×

Properties of unilevel block circulants. (English) Zbl 1217.15039

Summary: Let \({\mathcal A}=\{A_0,A_1,\dots,A_{k-1}\}\subset\mathbb C^{d_1\times d_2}\), \(\zeta=e^{-2\pi i/k}\), \(F_\ell=\sum^{k-1}_{m=0}\zeta^{\ell m}A_m\), \(0\leq \ell \leq k-1\), and \({\mathcal F}_A=\bigoplus^{k-1}_{\ell=0} F_\ell\). All operations in indices are modulo \(k\). It is well known that if \(d_1=d_2=1\) then \([A_{s-r}]^{k-1}_{r,s=0}=\Phi{\mathcal F}_A\Phi^k\), where \(\Phi=\frac{1}{\sqrt k}[\zeta^{\ell m}]^{k-1}_{\ell,m=0}\). However, to our knowledge it has not been emphasized that \({\mathcal F}_A\) plays a fundamental role in connection with all the matrices \([A_{s-\alpha r}]^{k-1}_{r,s=0}\), \(0\leq \alpha \leq k-1\), with \(d_1,d_2\) arbitrary. We begin by adapting a theorem of Ablow and Jenner with \(d_1=d_2=1\) to the case where \(d_1\) and \(d_2\) are arbitrary. We show that \(A=[A_{s-\alpha r}]^{k-1}_{r,s=0}\), if and only if \(A=U_\alpha{\mathcal F}_AP^*\) where \(U_\alpha\) and \(P\) are related to \(\Phi,P\) is unitary, and \(U_\alpha\) is invertible (in fact, unitary) if and only if gcd\((\alpha,k)=1\), in which case we say that \(A\) is a proper circulant. We prove the following for proper circulants \(A=[A_{s-\alpha r}]^{k-1}_{r,s=0}\): 8mm
(i)
\(A^\dagger=[B_{r-\alpha s}]^{k-1}_{r,s=0}\) with \(B_m=\frac1k\sum^{k-1}_{\ell=0}\zeta^{\ell m}F^\dagger_\ell\), \(0\leq m\leq k-1\).
(ii)
Solving \(Az=w\) reduces to solving \(F_\ell u_\ell=v_{\alpha\ell}\), \(0\leq \ell \leq k-1\), where \(v_0,v_1,\dots,v_{k-1}\) depend only on \(w\).
(iii)
A singular value decomposition of \(A\) can be obtained from singular value decompositions of \(F_0,F_1,\dots,F_{k-1}\).
(iv)
The least squares problem for \(A\) reduces to independent least squares problems for \(F_0,F_1,\dots,F_{k-1}\).
(v)
If \(d_1=d_2=d\), the eigenvalues of \([A_{s-r}]^{k-1}_{r,s=0}\) are the eigenvalues of \(F_0,F_1, \dots,F_{k-1}\), and the corresponding eigenvectors of \(A\) are easily obtainable from those of \(F_0,F_1,\dots,F_{k-1}\).
(vi)
If \(d_1=d_2=d\) and \(\alpha>1\) then the eigenvalue problem for \([A_{s-\alpha r}]^{k-1}_{r,s=0}\) reduces to eigenvalue problems for \(d\times d\) matrices related to \(F_0,F_1,\dots,F_{k-1}\) in a manner depending upon \(\alpha\).

MSC:

15B05 Toeplitz, Cauchy, and related matrices
65F20 Numerical solutions to overdetermined systems, pseudoinverses
15A09 Theory of matrix inversion and generalized inverses
65T50 Numerical methods for discrete and fast Fourier transforms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ablow, C. M.; Brenner, J. L., Roots and canonical forms for circulant matrices, Trans. Amer. Math. Soc., 107, 360-376 (1963) · Zbl 0112.25003
[2] Andrew, A. L., Eigenvectors of certain matrices, Linear Algebra Appl., 7, 151-162 (1973) · Zbl 0255.65021
[3] Ben-Israel, A.; Greville, T. N.E., Generalized Inverses: Theory and Applications (1974), John Wiley and Sons: John Wiley and Sons New York · Zbl 0305.15001
[4] Boman, E. C., The Moore-Penrose pseudoinverse of an arbitrary, square, \(k\)-circulant matrix, Linear and Multilinear Algebra, 50, 175-179 (2002) · Zbl 1002.15009
[5] Charmonman, S.; Julius, R. S., Explicit inverses and condition numbers of certain circulants, Math. Comput., 102, 428-430 (1968) · Zbl 0261.15002
[6] Davis, P. J., Cyclic transformations of polygons and the generalized inverse, Canad. J. Math., 29, 756-770 (1977) · Zbl 0368.15013
[7] Gray, R. M., Toeplitz and circulant matrices, Found. Trends Commun. Inform. Theory, 2, 155-239 (2006)
[8] Capizzano, S. Serra, A Korovkin-type theory for finite Toeplitz operators via matrix algebras, Numer. Math., 82, 117-142 (1999) · Zbl 0930.65024
[9] Capizzano, S. Serra, A Korovkin based approximation of multilevel Toeplitz matrices (with rectangular unstructured blocks) via multilevel trigonometric matrix spaces, SIAM J. Numer. Anal., 36, 1831-1857 (1999) · Zbl 0958.41016
[10] Stallings, W. T.; Boullion, T. L., The pseudoinverse of an \(r\)-circulant matrix, Proc. Amer. Math. Soc., 34, 385-388 (1972) · Zbl 0222.15002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.