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. 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]

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

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

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

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

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

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

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

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

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

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

Angelo B. Mingarelli. Nonlinear functionals in oscillation theory of matrix differential systems. Communications on Pure & Applied Analysis, 2004, 3 (1) : 75-84. doi: 10.3934/cpaa.2004.3.75
[16]

A. Cibotarica, Jiu Ding, J. Kolibal, Noah H. Rhee. Solutions of the Yang-Baxter matrix equation for an idempotent. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 347-352. doi: 10.3934/naco.2013.3.347
[17]

Leda Bucciantini, Angiolo Farina, Antonio Fasano. Flows in porous media with erosion of the solid matrix. Networks & Heterogeneous Media, 2010, 5 (1) : 63-95. doi: 10.3934/nhm.2010.5.63
[18]

Debasisha Mishra. Matrix group monotonicity using a dominance notion. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 267-274. doi: 10.3934/naco.2015.5.267
[19]

Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial & Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053
[20]

Joshua Du, Jun Ji. An integral representation of the determinant of a matrix and its applications. Conference Publications, 2005, 2005 (Special) : 225-232. doi: 10.3934/proc.2005.2005.225

2018 Impact Factor: 1.469

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences