30-2 Toeplitz matrices

A Toeplitz matrix is an \(n \times n\) matrix \(A = (a_{ij})\) such that \(a_{ij} = a_{i - 1, j - 1}\) for \(i = 2, 3, \dots, n\) and \(j = 2, 3, \dots, n\).

a. Is the sum of two Toeplitz matrices necessarily Toeplitz? What about the product?

b. Describe how to represent a Toeplitz matrix so that you can add two \(n \times n\) Toeplitz matrices in \(O(n)\) time.

c. Give an \(O(n\lg n)\)-time algorithm for multiplying an \(n \times n\) Toeplitz matrix by a vector of length \(n\). Use your representation from part (b).

d. Give an efficient algorithm for multiplying two \(n \times n\) Toeplitz matrices. Analyze its running time.

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用