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

Three steps on an open road

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.
Citation: Gilbert Strang. Three steps on an open road. Inverse Problems and 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.

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

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

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

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

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

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

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

[9]

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

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

[11]

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

[12]

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

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

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

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

[16]

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

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

[18]

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

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

[20]

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

[21]

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

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.

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

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

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

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

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

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

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

[9]

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

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

[11]

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

[12]

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

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

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

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

[16]

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

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

[18]

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

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

[20]

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

[21]

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

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

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 and Heterogeneous Media, 2020, 15 (1) : 1-28. doi: 10.3934/nhm.2020001

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

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

[8]

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

[9]

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

[10]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control and 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 and 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 and 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, 3 (4) : 769-791. doi: 10.3934/fods.2021028

[15]

Qinghua Wu, Guozheng Yan. The factorization method for a partially coated cavity in inverse scattering. Inverse Problems and 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 and 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 and 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 and 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 and Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052

2021 Impact Factor: 1.483

Metrics

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

Other articles
by authors

[Back to Top]