Groups of banded matrices with banded inverses

Strang, Gilbert

doi:10.1090/S0002-9939-2011-10959-6

Groups of banded matrices with banded inverses
HTML articles powered by AMS MathViewer

by Gilbert Strang

Proc. Amer. Math. Soc. 139 (2011), 4255-4264

DOI: https://doi.org/10.1090/S0002-9939-2011-10959-6

Published electronically: April 29, 2011

PDF | Request permission

Abstract:

A product $A=F_1 \ldots F_N$ of invertible block-diagonal matrices will be banded with a banded inverse: $A_ij=0$ and also $(A^{-1})_{ij}=0$ for $|i-j|>w$. We establish this factorization with the number $N$ controlled by the bandwidths $w$ and not by the matrix size $n.$ When $A$ is an orthogonal matrix, or a permutation, or banded plus finite rank, the factors $F_i$ have $w=1$ and we find generators of that corresponding group. In the case of infinite matrices, the $A=LPU$ factorization is now established but conjectures remain open.

References

C. Albert, C.-K. Li, G. Strang and G. Yu, Permutations as products of parallel transpositions, submitted to SIAM J. Discrete Math. (2010).
Edgar Asplund, Inverses of matrices $\{a_{ij}\}$ which satisfy $a_{ij}=0$ for $j>i+p$, Math. Scand. 7 (1959), 57–60. MR 109833, DOI 10.7146/math.scand.a-10561
Ingrid Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math. 41 (1988), no. 7, 909–996. MR 951745, DOI 10.1002/cpa.3160410705
I. Gohberg, M. A. Kaashoek, and I. M. Spitkovsky, An overview of matrix factorization theory and operator applications, Factorization and integrable systems (Faro, 2000) Oper. Theory Adv. Appl., vol. 141, Birkhäuser, Basel, 2003, pp. 1–102. MR 2021095
V. Olshevsky, G. Strang, and P. Zhlobich, Green’s matrices, Linear Algebra Appl. 432 (2010), no. 1, 218–241. MR 2566471, DOI 10.1016/j.laa.2009.07.038
G. Panova, Factorization of banded permutations, arXiv.org/abs/1007.1760 (2010).
J. Plemelj, Riemannsche Funktionenscharen mit gegebener Monodromiegruppe, Monatsh. Math. Phys. 19 (1908), no. 1, 211–245 (German). MR 1547764, DOI 10.1007/BF01736697
V.S.G. Raghavan, Banded Matrices with Banded Inverses, M.Sc. Thesis, MIT (2010).
M.D. Samson and M.F. Ezerman, Factoring permutation matrices into a product of tridiagonal matrices, arXiv.org/abs/1007.3467 (2010).
Gilbert Strang, Fast transforms: banded matrices with banded inverses, Proc. Natl. Acad. Sci. USA 107 (2010), no. 28, 12413–12416. MR 2670987, DOI 10.1073/pnas.1005493107
G. Strang, Banded matrices with banded inverses and A = LPU, Proceedings of ICCM2010 (International Congress of Chinese Mathematicians, Beijing, December 2010).
Gilbert Strang and Tri Nguyen, The interplay of ranks of submatrices, SIAM Rev. 46 (2004), no. 4, 637–646. MR 2124679, DOI 10.1137/S0036144503434381
K. TeKolste, private communication (2010).