American Institute of Mathematical Sciences

Advanced
August  2013, 7(3): 961-966. doi: 10.3934/ipi.2013.7.961

Three steps on an open road

Gilbert Strang 1,

1. 

Massachusetts Institute of Technology, Cambridge, MA 02139,, United States

Received  October 2012 Revised  December 2012 Published  September 2013

This note describes three recent factorizations of banded invertible infinite matrices
  1. If $A$ has a banded inverse;: $A = BC$ with block--diagonal factors $B$ and $C$.
  2. Permutations factor into a shift times $N < 2w$ tridiagonal permutations.
  3. $A = LPU$ with lower triangular $L$, permutation $P$, upper triangular $U$.
    We include examples and references and outlines of proofs.
Keywords: factorization., Banded matrix, elimination, banded inverse, doubly infinite matrix.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.
Citation: Gilbert Strang. Three steps on an open road. Inverse Problems & Imaging, 2013, 7 (3) : 961-966. doi: 10.3934/ipi.2013.7.961
References:
[1]

E. Asplund, Inverses of matrices {$a_{ij}$} which satisfy $a_{ij}=0$ for $j > i + p$, Math. Scand., 7 (1959), 57-60.  Google Scholar

[2]

S. N. Chandler-Wilde and M. Lindner, Limit Operators, Collective Compactness, and the Spectral Theory of Infinite Matrices, Amer. Math. Society Memoirs, 210 (2011). doi: 10.1090/S0065-9266-2010-00626-4.  Google Scholar

[3]

C. de Boor, What is the main diagonal of a biinfinite band matrix?, in "Quantitative Approximation" (eds. R. A. DeVore and K. Scherer), Academic Press, 1980. Google Scholar

[4]

L. Elsner, On some algebraic problems in connection with general eigenvalue algorithms, Lin. Alg. Appl., 26 (1979), 123-138. doi: 10.1016/0024-3795(79)90175-7.  Google Scholar

[5]

I. Gohberg and S. Goldberg, Finite dimensional Wiener-Hopf equations and factorizations of matrices, Lin. Alg. Appl., 48 (1982), 219-236. doi: 10.1016/0024-3795(82)90109-4.  Google Scholar

[6]

I. Gohberg, S. Goldberg and M. A. Kaashoek, "Basic Classes of Linear Operators," Birkhäuser Verlag, Basel, 2003. doi: 10.1007/978-3-0348-7980-4.  Google Scholar

[7]

I. Gohberg, M. Kaashoek and I. Spitkovsky, An overview of matrix factorization theory and operator application, in "Factorization and Integrable Systems" (Faro, 2000), Operator Th. Adv. Appl., 141, Birkhäuser, Basel, (2003), 1-102.  Google Scholar

[8]

L. Yu. Kolotilina and A. Yu. Yeremin, Bruhat decomposition and solution of sparse linear algebra systems, Soviet J. Numer. Anal. Math. Modelling, 2 (1987), 421-436.  Google Scholar

[9]

M. Lindner, "Infinite Matrices and Their Finite Sections. An Introduction to the Limit Operator Method," Frontiers in Mathematics, Birkhäuser Verlag, Basel, 2006.  Google Scholar

[10]

M. Lindner and G. Strang, The main diagonal of a permutation matrix, Linear Algebra and Its Applications, 439 (2013), 524-537. doi: 10.1016/j.laa.2012.02.034.  Google Scholar

[11]

G. Panova, Factorization of banded permutations, Proceedings Amer. Math. Soc., 140 (2012), 3805-3812. doi: 10.1090/S0002-9939-2012-11411-X.  Google Scholar

[12]

J. Plemelj, Riemannsche Funktionenscharen mit gegebener Monodromiegruppe, Monat. Math. Phys., 19 (1908), 211-245. doi: 10.1007/BF01736697.  Google Scholar

[13]

V. S. Rabinovich, S. Roch and J. Roe, Fredholm indices of band-dominated operators, Integral Eqns. Oper. Th., 49 (2004), 221-238. doi: 10.1007/s00020-003-1285-1.  Google Scholar

[14]

V. S. Rabinovich, S. Roch and B. Silbermann, "Limit Operators and Their Applications in Operator Theory," Operator Theory: Advances and Applications, 150, Birkhäuser Verlag, Basel, 2004. doi: 10.1007/978-3-0348-7911-8.  Google Scholar

[15]

V. S. Rabinovich, S. Roch and B. Silbermann, The finite section approach to the index formula for band-dominated operators, Operator Theory, 187 (2008), 185-193. doi: 10.1007/978-3-7643-8893-5_11.  Google Scholar

[16]

S. Roch, Finite sections of band-dominated operators, AMS Memoirs, 191 (2008). doi: 10.1090/memo/0895.  Google Scholar

[17]

G. Strang, Banded matrices with banded inverses and $A=LPU$, in "Fifth International Congress of Chinese Mathematicians. Part 1, 2," AMS/IP Studies in Advanced Mathematics, 51, American Math. Society, Providence, RI, (2012), 771-784.  Google Scholar

[18]

G. Strang, Fast transforms: Banded matrices with banded inverses, Proc. Natl. Acad. Sci., 107 (2010), 12413-12416. doi: 10.1073/pnas.1005493107.  Google Scholar

[19]

G. Strang, Groups of banded matrices with banded inverses, Proceedings Amer. Math. Soc., 139 (2011), 4255-4264. doi: 10.1090/S0002-9939-2011-10959-6.  Google Scholar

[20]

G. Strang, The algebra of elimination, manuscript, 2012. Google Scholar

[21]

G. Strang and Tri-Dung Nguyen, The interplay of ranks of submatrices, SIAM Review, 46 (2004), 637-646. doi: 10.1137/S0036144503434381.  Google Scholar

show all references

References:
[1]

E. Asplund, Inverses of matrices {$a_{ij}$} which satisfy $a_{ij}=0$ for $j > i + p$, Math. Scand., 7 (1959), 57-60.  Google Scholar

[2]

S. N. Chandler-Wilde and M. Lindner, Limit Operators, Collective Compactness, and the Spectral Theory of Infinite Matrices, Amer. Math. Society Memoirs, 210 (2011). doi: 10.1090/S0065-9266-2010-00626-4.  Google Scholar

[3]

C. de Boor, What is the main diagonal of a biinfinite band matrix?, in "Quantitative Approximation" (eds. R. A. DeVore and K. Scherer), Academic Press, 1980. Google Scholar

[4]

L. Elsner, On some algebraic problems in connection with general eigenvalue algorithms, Lin. Alg. Appl., 26 (1979), 123-138. doi: 10.1016/0024-3795(79)90175-7.  Google Scholar

[5]

I. Gohberg and S. Goldberg, Finite dimensional Wiener-Hopf equations and factorizations of matrices, Lin. Alg. Appl., 48 (1982), 219-236. doi: 10.1016/0024-3795(82)90109-4.  Google Scholar

[6]

I. Gohberg, S. Goldberg and M. A. Kaashoek, "Basic Classes of Linear Operators," Birkhäuser Verlag, Basel, 2003. doi: 10.1007/978-3-0348-7980-4.  Google Scholar

[7]

I. Gohberg, M. Kaashoek and I. Spitkovsky, An overview of matrix factorization theory and operator application, in "Factorization and Integrable Systems" (Faro, 2000), Operator Th. Adv. Appl., 141, Birkhäuser, Basel, (2003), 1-102.  Google Scholar

[8]

L. Yu. Kolotilina and A. Yu. Yeremin, Bruhat decomposition and solution of sparse linear algebra systems, Soviet J. Numer. Anal. Math. Modelling, 2 (1987), 421-436.  Google Scholar

[9]

M. Lindner, "Infinite Matrices and Their Finite Sections. An Introduction to the Limit Operator Method," Frontiers in Mathematics, Birkhäuser Verlag, Basel, 2006.  Google Scholar

[10]

M. Lindner and G. Strang, The main diagonal of a permutation matrix, Linear Algebra and Its Applications, 439 (2013), 524-537. doi: 10.1016/j.laa.2012.02.034.  Google Scholar

[11]

G. Panova, Factorization of banded permutations, Proceedings Amer. Math. Soc., 140 (2012), 3805-3812. doi: 10.1090/S0002-9939-2012-11411-X.  Google Scholar

[12]

J. Plemelj, Riemannsche Funktionenscharen mit gegebener Monodromiegruppe, Monat. Math. Phys., 19 (1908), 211-245. doi: 10.1007/BF01736697.  Google Scholar

[13]

V. S. Rabinovich, S. Roch and J. Roe, Fredholm indices of band-dominated operators, Integral Eqns. Oper. Th., 49 (2004), 221-238. doi: 10.1007/s00020-003-1285-1.  Google Scholar

[14]

V. S. Rabinovich, S. Roch and B. Silbermann, "Limit Operators and Their Applications in Operator Theory," Operator Theory: Advances and Applications, 150, Birkhäuser Verlag, Basel, 2004. doi: 10.1007/978-3-0348-7911-8.  Google Scholar

[15]

V. S. Rabinovich, S. Roch and B. Silbermann, The finite section approach to the index formula for band-dominated operators, Operator Theory, 187 (2008), 185-193. doi: 10.1007/978-3-7643-8893-5_11.  Google Scholar

[16]

S. Roch, Finite sections of band-dominated operators, AMS Memoirs, 191 (2008). doi: 10.1090/memo/0895.  Google Scholar

[17]

G. Strang, Banded matrices with banded inverses and $A=LPU$, in "Fifth International Congress of Chinese Mathematicians. Part 1, 2," AMS/IP Studies in Advanced Mathematics, 51, American Math. Society, Providence, RI, (2012), 771-784.  Google Scholar

[18]

G. Strang, Fast transforms: Banded matrices with banded inverses, Proc. Natl. Acad. Sci., 107 (2010), 12413-12416. doi: 10.1073/pnas.1005493107.  Google Scholar

[19]

G. Strang, Groups of banded matrices with banded inverses, Proceedings Amer. Math. Soc., 139 (2011), 4255-4264. doi: 10.1090/S0002-9939-2011-10959-6.  Google Scholar

[20]

G. Strang, The algebra of elimination, manuscript, 2012. Google Scholar

[21]

G. Strang and Tri-Dung Nguyen, The interplay of ranks of submatrices, SIAM Review, 46 (2004), 637-646. doi: 10.1137/S0036144503434381.  Google Scholar

[1]

Peizhao Yu, Guoshan Zhang. Eigenstructure assignment for polynomial matrix systems ensuring normalization and impulse elimination. Mathematical Foundations of Computing, 2019, 2 (3) : 251-266. doi: 10.3934/mfc.2019016
[2]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025
[3]

Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601
[4]

Sonia Martínez, Jorge Cortés, Francesco Bullo. A catalog of inverse-kinematics planners for underactuated systems on matrix groups. Journal of Geometric Mechanics, 2009, 1 (4) : 445-460. doi: 10.3934/jgm.2009.1.445
[5]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[6]

Travis G. Draper, Fernando Guevara Vasquez, Justin Cheuk-Lum Tse, Toren E. Wallengren, Kenneth Zheng. Matrix valued inverse problems on graphs with application to mass-spring-damper systems. Networks & Heterogeneous Media, 2020, 15 (1) : 1-28. doi: 10.3934/nhm.2020001
[7]

Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009
[8]

Paul Skerritt, Cornelia Vizman. Dual pairs for matrix groups. Journal of Geometric Mechanics, 2019, 11 (2) : 255-275. doi: 10.3934/jgm.2019014
[9]

Adel Alahmadi, Hamed Alsulami, S.K. Jain, Efim Zelmanov. On matrix wreath products of algebras. Electronic Research Announcements, 2017, 24: 78-86. doi: 10.3934/era.2017.24.009
[10]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015
[11]

K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026
[12]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[13]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[14]

Henry Adams, Lara Kassab, Deanna Needell. An adaptation for iterative structured matrix completion. Foundations of Data Science, 2021  doi: 10.3934/fods.2021028
[15]

Qinghua Wu, Guozheng Yan. The factorization method for a partially coated cavity in inverse scattering. Inverse Problems & Imaging, 2016, 10 (1) : 263-279. doi: 10.3934/ipi.2016.10.263
[16]

Lei Zhang, Anfu Zhu, Aiguo Wu, Lingling Lv. Parametric solutions to the regulator-conjugate matrix equations. Journal of Industrial & Management Optimization, 2017, 13 (2) : 623-631. doi: 10.3934/jimo.2016036
[17]

Heide Gluesing-Luerssen, Fai-Lung Tsang. A matrix ring description for cyclic convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 55-81. doi: 10.3934/amc.2008.2.55
[18]

Houduo Qi, ZHonghang Xia, Guangming Xing. An application of the nearest correlation matrix on web document classification. Journal of Industrial & Management Optimization, 2007, 3 (4) : 701-713. doi: 10.3934/jimo.2007.3.701
[19]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103
[20]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (126)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy