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.   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, (1980).   Google Scholar

[4]

L. Elsner, On some algebraic problems in connection with general eigenvalue algorithms,, Lin. Alg. Appl., 26 (1979), 123.  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.  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, (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, 141 (2003), 1.   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.   Google Scholar

[9]

M. Lindner, "Infinite Matrices and Their Finite Sections. An Introduction to the Limit Operator Method,", Frontiers in Mathematics, (2006).   Google Scholar

[10]

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

[11]

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

[12]

J. Plemelj, Riemannsche Funktionenscharen mit gegebener Monodromiegruppe,, Monat. Math. Phys., 19 (1908), 211.  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.  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 (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.  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, 51 (2012), 771.   Google Scholar

[18]

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

[19]

G. Strang, Groups of banded matrices with banded inverses,, Proceedings Amer. Math. Soc., 139 (2011), 4255.  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.  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.   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, (1980).   Google Scholar

[4]

L. Elsner, On some algebraic problems in connection with general eigenvalue algorithms,, Lin. Alg. Appl., 26 (1979), 123.  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.  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, (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, 141 (2003), 1.   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.   Google Scholar

[9]

M. Lindner, "Infinite Matrices and Their Finite Sections. An Introduction to the Limit Operator Method,", Frontiers in Mathematics, (2006).   Google Scholar

[10]

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

[11]

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

[12]

J. Plemelj, Riemannsche Funktionenscharen mit gegebener Monodromiegruppe,, Monat. Math. Phys., 19 (1908), 211.  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.  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 (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.  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, 51 (2012), 771.   Google Scholar

[18]

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

[19]

G. Strang, Groups of banded matrices with banded inverses,, Proceedings Amer. Math. Soc., 139 (2011), 4255.  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.  doi: 10.1137/S0036144503434381.  Google Scholar

[1]

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
[2]

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
[3]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[4]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435
[5]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375
[6]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[7]

Nalin Fonseka, Jerome Goddard II, Ratnasingham Shivaji, Byungjae Son. A diffusive weak Allee effect model with U-shaped emigration and matrix hostility. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020356
[8]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076
[9]

Yueh-Cheng Kuo, Huan-Chang Cheng, Jhih-You Syu, Shih-Feng Shieh. On the nearest stable $ 2\times 2 $ matrix, dedicated to Prof. Sze-Bi Hsu in appreciation of his inspiring ideas. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020358
[10]

Franck Davhys Reval Langa, Morgan Pierre. A doubly splitting scheme for the Caginalp system with singular potentials and dynamic boundary conditions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 653-676. doi: 10.3934/dcdss.2020353
[11]

Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial & Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123
[12]

Hai Huang, Xianlong Fu. Optimal control problems for a neutral integro-differential system with infinite delay. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020107
[13]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[14]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380
[15]

Qingfeng Zhu, Yufeng Shi. Nonzero-sum differential game of backward doubly stochastic systems with delay and applications. Mathematical Control & Related Fields, 2021, 11 (1) : 73-94. doi: 10.3934/mcrf.2020028
[16]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216
[17]

Max E. Gilmore, Chris Guiver, Hartmut Logemann. Sampled-data integral control of multivariable linear infinite-dimensional systems with input nonlinearities. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021001
[18]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108
[19]

Gongbao Li, Tao Yang. Improved Sobolev inequalities involving weighted Morrey norms and the existence of nontrivial solutions to doubly critical elliptic systems involving fractional Laplacian and Hardy terms. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020469
[20]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072

2019 Impact Factor: 1.373

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences