Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Tridiagonal matrix
open-in-new
<h2 id="properties">Properties</h2> <p>A tridiagonal matrix is a matrix that is both upper and lower <a href="/facts/Hessenberg_matrix/vy7p7s3Y">Hessenberg matrix</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> In particular, a tridiagonal matrix is a <a href="/facts/Direct_sum/x3ljVsP6">direct sum</a> of <i>p</i> 1-by-1 and <i>q</i> 2-by-2 matrices such that <i>p</i> + <i>q</i>/2 = <i>n</i> — the dimension of the tridiagonal. Although a general tridiagonal matrix is not necessarily <a href="/facts/Symmetric_matrix/08CGwjNl">symmetric</a> or <a href="/facts/Hermitian_matrix/qArPblYo">Hermitian</a>, many of those that arise when solving linear algebra problems have one of these properties. Furthermore, if a real tridiagonal matrix <i>A</i> satisfies <i>a</i><i>k</i>,<i>k</i>+1 <i>a</i><i>k</i>+1,<i>k</i> > 0 for all <i>k</i>, so that the signs of its entries are symmetric, then it is <a href="/facts/Similar_(linear_algebra)/ySevpav1">similar</a> to a Hermitian matrix, by a diagonal change of basis matrix. Hence, its <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalues</a> are real. If we replace the strict inequality by <i>a</i><i>k</i>,<i>k</i>+1 <i>a</i><i>k</i>+1,<i>k</i> ≥ 0, then by continuity, the eigenvalues are still guaranteed to be real, but the matrix need no longer be similar to a Hermitian matrix.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>The <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of all <i>n × n</i> tridiagonal matrices forms a <i>3n-2</i> <a href="/facts/Dimensional/0ktmUyac">dimensional</a> <a href="/facts/Vector_space/M1pxMLx2">vector space</a>. </p><p>Many linear algebra <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> require significantly less <a href="/facts/Computational_complexity_theory/etHuVF3U">computational effort</a> when applied to diagonal matrices, and this improvement often carries over to tridiagonal matrices as well. </p> <h3>Determinant</h3> <p class="note">Main article: <a href="/facts/Continuant_(mathematics)/lw7mt8Kt">Continuant (mathematics)</a></p> <p>The <a href="/facts/Determinant/eGYqJ2TF">determinant</a> of a tridiagonal matrix <i>A</i> of order <i>n</i> can be computed from a three-term <a href="/facts/Recurrence_relation/JolXC71M">recurrence relation</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Write <i>f</i>1 = |<i>a</i>1| = <i>a</i>1 (i.e., <i>f</i>1 is the determinant of the 1 by 1 matrix consisting only of <i>a</i>1), and let </p> f n = | a 1 b 1 c 1 a 2 b 2 c 2 ⋱ ⋱ ⋱ ⋱ b n − 1 c n − 1 a n | . {\displaystyle f_{n}={\begin{vmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{vmatrix}}.} <p>The sequence (<i>f</i><i>i</i>) is called the <a href="/facts/Continuant_(mathematics)/lw7mt8Kt">continuant</a> and satisfies the recurrence relation </p> f n = a n f n − 1 − c n − 1 b n − 1 f n − 2 {\displaystyle f_{n}=a_{n}f_{n-1}-c_{n-1}b_{n-1}f_{n-2}} <p>with initial values <i>f</i>0 = 1 and <i>f</i>−1 = 0. The cost of computing the determinant of a tridiagonal matrix using this formula is linear in <i>n</i>, while the cost is cubic for a general matrix. </p> <h3>Inversion</h3> <p>The <a href="/facts/Inverse_matrix/fPqXk3V8">inverse</a> of a non-singular tridiagonal matrix <i>T</i> </p> T = ( a 1 b 1 c 1 a 2 b 2 c 2 ⋱ ⋱ ⋱ ⋱ b n − 1 c n − 1 a n ) {\displaystyle T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}} <p>is given by </p> ( T − 1 ) i j = { ( − 1 ) i + j b i ⋯ b j − 1 θ i − 1 ϕ j + 1 / θ n if i < j θ i − 1 ϕ j + 1 / θ n if i = j ( − 1 ) i + j c j ⋯ c i − 1 θ j − 1 ϕ i + 1 / θ n if i > j {\displaystyle (T^{-1})_{ij}={\begin{cases}(-1)^{i+j}b_{i}\cdots b_{j-1}\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i<j\\\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i=j\\(-1)^{i+j}c_{j}\cdots c_{i-1}\theta _{j-1}\phi _{i+1}/\theta _{n}&{\text{ if }}i>j\\\end{cases}}} <p>where the <i>θi</i> satisfy the recurrence relation </p> θ i = a i θ i − 1 − b i − 1 c i − 1 θ i − 2 i = 2 , 3 , … , n {\displaystyle \theta _{i}=a_{i}\theta _{i-1}-b_{i-1}c_{i-1}\theta _{i-2}\qquad i=2,3,\ldots ,n} <p>with initial conditions <i>θ</i>0 = 1, <i>θ</i>1 = <i>a</i>1 and the <i>ϕ</i><i>i</i> satisfy </p> ϕ i = a i ϕ i + 1 − b i c i ϕ i + 2 i = n − 1 , … , 1 {\displaystyle \phi _{i}=a_{i}\phi _{i+1}-b_{i}c_{i}\phi _{i+2}\qquad i=n-1,\ldots ,1} <p>with initial conditions <i>ϕ</i><i>n</i>+1 = 1 and <i>ϕ</i><i>n</i> = <i>an</i>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p><p>Closed form solutions can be computed for special cases such as <a href="/facts/Symmetric_matrix/08CGwjNl">symmetric matrices</a> with all diagonal and off-diagonal elements equal<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> or <a href="/facts/Toeplitz_matrices/WAjSdlaW">Toeplitz matrices</a><a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> and for the general case as well.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a><a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p><p>In general, the inverse of a tridiagonal matrix is a semiseparable matrix and vice versa.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> The inverse of a symmetric tridiagonal matrix can be written as a single-pair matrix (a.k.a. <i>generator-representable semiseparable matrix</i>) of the form<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p><p> ( α 1 − β 1 − β 1 α 2 − β 2 ⋱ ⋱ ⋱ ⋱ ⋱ − β n − 1 − β n − 1 α n ) − 1 = ( a 1 b 1 a 1 b 2 ⋯ a 1 b n a 1 b 2 a 2 b 2 ⋯ a 2 b n ⋮ ⋮ ⋱ ⋮ a 1 b n a 2 b n ⋯ a n b n ) = ( a min ( i , j ) b max ( i , j ) ) {\displaystyle {\begin{pmatrix}\alpha _{1}&-\beta _{1}\\-\beta _{1}&\alpha _{2}&-\beta _{2}\\&\ddots &\ddots &\ddots &\\&&\ddots &\ddots &-\beta _{n-1}\\&&&-\beta _{n-1}&\alpha _{n}\end{pmatrix}}^{-1}={\begin{pmatrix}a_{1}b_{1}&a_{1}b_{2}&\cdots &a_{1}b_{n}\\a_{1}b_{2}&a_{2}b_{2}&\cdots &a_{2}b_{n}\\\vdots &\vdots &\ddots &\vdots \\a_{1}b_{n}&a_{2}b_{n}&\cdots &a_{n}b_{n}\end{pmatrix}}=\left(a_{\min(i,j)}b_{\max(i,j)}\right)} </p><p>where { a i = β i ⋯ β n − 1 δ i ⋯ δ n b n b i = β 1 ⋯ β i − 1 d 1 ⋯ d i {\displaystyle {\begin{cases}\displaystyle a_{i}={\frac {\beta _{i}\cdots \beta _{n-1}}{\delta _{i}\cdots \delta _{n}\,b_{n}}}\\\displaystyle b_{i}={\frac {\beta _{1}\cdots \beta _{i-1}}{d_{1}\cdots d_{i}}}\end{cases}}} with { d n = α n , d i − 1 = α i − 1 − β i − 1 2 d i , i = n , n − 1 , ⋯ , 2 , δ 1 = α 1 , δ i + 1 = α i + 1 − β i 2 δ i , i = 1 , 2 , ⋯ , n − 1. {\displaystyle {\begin{cases}d_{n}=\alpha _{n},\quad d_{i-1}=\alpha _{i-1}-{\frac {\beta _{i-1}^{2}}{d_{i}}},&i=n,n-1,\cdots ,2,\\\delta _{1}=\alpha _{1},\quad \delta _{i+1}=\alpha _{i+1}-{\frac {\beta _{i}^{2}}{\delta _{i}}},&i=1,2,\cdots ,n-1.\end{cases}}} </p> <h3>Solution of linear system</h3> <p class="note">Main article: <a href="/facts/Tridiagonal_matrix_algorithm/NREF5x1c">tridiagonal matrix algorithm</a></p> <p>A system of equations <i>Ax</i> = <i>b</i> for b ∈ R n {\displaystyle b\in \mathbb {R} ^{n}} can be solved by an efficient form of Gaussian elimination when <i>A</i> is tridiagonal called <a href="/facts/Tridiagonal_matrix_algorithm/NREF5x1c">tridiagonal matrix algorithm</a>, requiring <i>O</i>(<i>n</i>) operations.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> </p> <h3>Eigenvalues</h3> <p>When a tridiagonal matrix is also <a href="/facts/Toeplitz_matrix/WAjSdlaW">Toeplitz</a>, there is a simple closed-form solution for its eigenvalues, namely:<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a><a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> </p> a − 2 b c cos ( k π n + 1 ) , k = 1 , … , n . {\displaystyle a-2{\sqrt {bc}}\cos \left({\frac {k\pi }{n+1}}\right),\qquad k=1,\ldots ,n.} <p>A real <a href="/facts/Symmetric_matrix/08CGwjNl">symmetric</a> tridiagonal matrix has real eigenvalues, and all the eigenvalues are <a href="/facts/Eigenvalues_and_eigenvectors/8TjEoT8u">distinct (simple)</a> if all off-diagonal elements are nonzero.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> Numerous methods exist for the numerical computation of the eigenvalues of a real symmetric tridiagonal matrix to arbitrary finite precision, typically requiring O ( n 2 ) {\displaystyle O(n^{2})} operations for a matrix of size n × n {\displaystyle n\times n} , although fast algorithms exist which (without parallel computation) require only O ( n log n ) {\displaystyle O(n\log n)} .<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> </p><p>As a side note, an <i>unreduced</i> symmetric tridiagonal matrix is a matrix containing non-zero off-diagonal elements of the tridiagonal, where the eigenvalues are distinct while the eigenvectors are unique up to a scale factor and are mutually orthogonal.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> </p> <h3>Similarity to symmetric tridiagonal matrix</h3> <p>For <i>unsymmetric</i> or <i>nonsymmetric</i> tridiagonal matrices one can compute the eigendecomposition using a similarity transformation. Given a real tridiagonal, nonsymmetric matrix </p> T = ( a 1 b 1 c 1 a 2 b 2 c 2 ⋱ ⋱ ⋱ ⋱ b n − 1 c n − 1 a n ) {\displaystyle T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}} <p>where b i ≠ c i {\displaystyle b_{i}\neq c_{i}} . Assume that each product of off-diagonal entries is strictly positive b i c i > 0 {\displaystyle b_{i}c_{i}>0} and define a transformation matrix D {\displaystyle D} by<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> </p> D := diag ( δ 1 , … , δ n ) for δ i := { 1 , i = 1 c i − 1 … c 1 b i − 1 … b 1 , i = 2 , … , n . {\displaystyle D:=\operatorname {diag} (\delta _{1},\dots ,\delta _{n})\quad {\text{for}}\quad \delta _{i}:={\begin{cases}1&,\,i=1\\{\sqrt {\frac {c_{i-1}\dots c_{1}}{b_{i-1}\dots b_{1}}}}&,\,i=2,\dots ,n\,.\end{cases}}} <p>The <a href="/facts/Matrix_similarity/ySevpav1">similarity transformation</a> D − 1 T D {\displaystyle D^{-1}TD} yields a <i>symmetric</i> tridiagonal matrix J {\displaystyle J} by:<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a><a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> </p> J := D − 1 T D = ( a 1 sgn b 1 b 1 c 1 sgn b 1 b 1 c 1 a 2 sgn b 2 b 2 c 2 sgn b 2 b 2 c 2 ⋱ ⋱ ⋱ ⋱ sgn b n − 1 b n − 1 c n − 1 sgn b n − 1 b n − 1 c n − 1 a n ) . {\displaystyle J:=D^{-1}TD={\begin{pmatrix}a_{1}&\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}\\\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}&a_{2}&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}\\&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}&\ddots &\ddots \\&&\ddots &\ddots &\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}\\&&&\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}&a_{n}\end{pmatrix}}\,.} <p>Note that T {\displaystyle T} and J {\displaystyle J} have the same eigenvalues. </p> <h2 id="computer-programming">Computer programming</h2> <p>A transformation that reduces a general matrix to Hessenberg form will reduce a Hermitian matrix to tridiagonal form. So, many <a href="/facts/Eigenvalue_algorithm/AYecadB0">eigenvalue algorithms</a>, when applied to a Hermitian matrix, reduce the input Hermitian matrix to (symmetric real) tridiagonal form as a first step.<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> </p><p>A tridiagonal matrix can also be stored more efficiently than a general matrix by using a special <a href="/facts/Matrix_representation/nGwsmpMt">storage scheme</a>. For instance, the <a href="/facts/LAPACK/sMGe0RhF">LAPACK</a> <a href="/facts/Fortran/m1KqjcMU">Fortran</a> package stores an unsymmetric tridiagonal matrix of order <i>n</i> in three one-dimensional arrays, one of length <i>n</i> containing the diagonal elements, and two of length <i>n</i> − 1 containing the <a href="/facts/Subdiagonal/39z9sIRb">subdiagonal</a> and <a href="/facts/Superdiagonal/39z9sIRb">superdiagonal</a> elements. </p> <h2 id="applications">Applications</h2> <p>The discretization in space of the one-dimensional diffusion or <a href="/facts/Heat_equation/2JPPr5GG">heat equation</a> </p> ∂ u ( t , x ) ∂ t = α ∂ 2 u ( t , x ) ∂ x 2 {\displaystyle {\frac {\partial u(t,x)}{\partial t}}=\alpha {\frac {\partial ^{2}u(t,x)}{\partial x^{2}}}} <p>using second order central <a href="/facts/Finite_differences/aY1txFhj">finite differences</a> results in </p> ( ∂ u 1 ( t ) ∂ t ∂ u 2 ( t ) ∂ t ⋮ ∂ u N ( t ) ∂ t ) = α Δ x 2 ( − 2 1 0 … 0 1 − 2 1 ⋱ ⋮ 0 ⋱ ⋱ ⋱ 0 ⋮ 1 − 2 1 0 … 0 1 − 2 ) ( u 1 ( t ) u 2 ( t ) ⋮ u N ( t ) ) {\displaystyle {\begin{pmatrix}{\frac {\partial u_{1}(t)}{\partial t}}\\{\frac {\partial u_{2}(t)}{\partial t}}\\\vdots \\{\frac {\partial u_{N}(t)}{\partial t}}\end{pmatrix}}={\frac {\alpha }{\Delta x^{2}}}{\begin{pmatrix}-2&1&0&\ldots &0\\1&-2&1&\ddots &\vdots \\0&\ddots &\ddots &\ddots &0\\\vdots &&1&-2&1\\0&\ldots &0&1&-2\end{pmatrix}}{\begin{pmatrix}u_{1}(t)\\u_{2}(t)\\\vdots \\u_{N}(t)\\\end{pmatrix}}} <p>with discretization constant Δ x {\displaystyle \Delta x} . The matrix is tridiagonal with a i = − 2 {\displaystyle a_{i}=-2} and b i = c i = 1 {\displaystyle b_{i}=c_{i}=1} . Note: no boundary conditions are used here. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Pentadiagonal_matrix/S5khQsbp">Pentadiagonal matrix</a></li> <li><a href="/facts/Jacobi_matrix_(operator)/FtG47pD7">Jacobi matrix (operator)</a></li></ul> <h2 id="notes">Notes</h2> <h2 id="external-links">External links</h2> <ul><li><a href="http://www.netlib.org/lapack/lug/node125.html">Tridiagonal and Bidiagonal Matrices</a> in the LAPACK manual.</li> <li>Moawwad El-Mikkawy, Abdelrahman Karawia (2006). <a href="https://doi.org/10.1016%2Fj.aml.2005.11.012">"Inversion of general tridiagonal matrices"</a>. <i>Applied Mathematics Letters</i>. 19 (8): 712–720. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.aml.2005.11.012">10.1016/j.aml.2005.11.012</a>.</li> <li><a href="http://www.cs.utexas.edu/users/flame/pubs/flawn53.pdf">High performance algorithms</a> for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form</li> <li><a href="https://web.archive.org/web/20140310122757/http://michal.is/projects/tridiagonal-system-solver-sor-c/">Tridiagonal linear system solver</a> in C++</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Thomas Muir (1960). A treatise on the theory of determinants. Dover Publications. pp. 516–525. <a href="/wiki/Thomas_Muir_(mathematician)" target="_blank">/wiki/Thomas_Muir_(mathematician)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. p. 28. ISBN 0521386322. <a href="0521386322" target="_blank">0521386322</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Horn & Johnson, page 174 <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>El-Mikkawy, M. E. A. (2004). "On the inverse of a general tridiagonal matrix". Applied Mathematics and Computation. 150 (3): 669–679. doi:10.1016/S0096-3003(03)00298-4. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Da Fonseca, C. M. (2007). "On the eigenvalues of some tridiagonal matrices". Journal of Computational and Applied Mathematics. 200: 283–286. doi:10.1016/j.cam.2005.08.047. <a href="https://doi.org/10.1016%2Fj.cam.2005.08.047" target="_blank">https://doi.org/10.1016%2Fj.cam.2005.08.047</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Usmani, R. A. (1994). "Inversion of a tridiagonal jacobi matrix". Linear Algebra and Its Applications. 212–213: 413–414. doi:10.1016/0024-3795(94)90414-6. <a href="https://doi.org/10.1016%2F0024-3795%2894%2990414-6" target="_blank">https://doi.org/10.1016%2F0024-3795%2894%2990414-6</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Hu, G. Y.; O'Connell, R. F. (1996). "Analytical inversion of symmetric tridiagonal matrices". Journal of Physics A: Mathematical and General. 29 (7): 1511. Bibcode:1996JPhA...29.1511H. doi:10.1088/0305-4470/29/7/020. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Huang, Y.; McColl, W. F. (1997). "Analytical inversion of general tridiagonal matrices". Journal of Physics A: Mathematical and General. 30 (22): 7919. Bibcode:1997JPhA...30.7919H. doi:10.1088/0305-4470/30/22/026. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Mallik, R. K. (2001). "The inverse of a tridiagonal matrix". Linear Algebra and Its Applications. 325 (1–3): 109–139. doi:10.1016/S0024-3795(00)00262-7. <a href="https://doi.org/10.1016%2FS0024-3795%2800%2900262-7" target="_blank">https://doi.org/10.1016%2FS0024-3795%2800%2900262-7</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Kılıç, E. (2008). "Explicit formula for the inverse of a tridiagonal matrix by backward continued fractions". Applied Mathematics and Computation. 197: 345–357. doi:10.1016/j.amc.2007.07.046. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Raf Vandebril; Marc Van Barel; Nicola Mastronardi (2008). Matrix Computations and Semiseparable Matrices. Volume I: Linear Systems. JHU Press. Theorem 1.38, p. 41. ISBN 978-0-8018-8714-7. <a href="978-0-8018-8714-7" target="_blank">978-0-8018-8714-7</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Meurant, Gerard (1992). "A review on the inverse of symmetric tridiagonal and block tridiagonal matrices". SIAM Journal on Matrix Analysis and Applications. 13 (3): 707–728. doi:10.1137/0613045. <a href="https://doi.org/10.1137/0613045" target="_blank">https://doi.org/10.1137/0613045</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Bossu, Sebastien (2024). "Tridiagonal and single-pair matrices and the inverse sum of two single-pair matrices". Linear Algebra and Its Applications. 699: 129–158. arXiv:2304.06100. doi:10.1016/j.laa.2024.06.018. <a href="https://authors.elsevier.com/a/1jOTP5YnCtZEc" target="_blank">https://authors.elsevier.com/a/1jOTP5YnCtZEc</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). The Johns Hopkins University Press. ISBN 0-8018-5414-8. <a href="0-8018-5414-8" target="_blank">0-8018-5414-8</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Noschese, S.; Pasquini, L.; Reichel, L. (2013). "Tridiagonal Toeplitz matrices: Properties and novel applications". Numerical Linear Algebra with Applications. 20 (2): 302. doi:10.1002/nla.1811. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>This can also be written as a + 2 b c cos ( k π / ( n + 1 ) ) {\displaystyle a+2{\sqrt {bc}}\cos(k\pi /{(n+1)})} because cos ( x ) = − cos ( π − x ) {\displaystyle \cos(x)=-\cos(\pi -x)} , as is done in: Kulkarni, D.; Schmidt, D.; Tsui, S. K. (1999). "Eigenvalues of tridiagonal pseudo-Toeplitz matrices" (PDF). Linear Algebra and Its Applications. 297 (1–3): 63–80. doi:10.1016/S0024-3795(99)00114-7. <a href="https://hal.archives-ouvertes.fr/hal-01461924/file/KST.pdf" target="_blank">https://hal.archives-ouvertes.fr/hal-01461924/file/KST.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Parlett, B.N. (1997) [1980]. The Symmetric Eigenvalue Problem. Classics in applied mathematics. Vol. 20. SIAM. ISBN 0-89871-402-8. OCLC 228147822. <a href="0-89871-402-8" target="_blank">0-89871-402-8</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Coakley, E.S.; Rokhlin, V. (2012). "A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices". Applied and Computational Harmonic Analysis. 34 (3): 379–414. doi:10.1016/j.acha.2012.06.003. <a href="https://doi.org/10.1016%2Fj.acha.2012.06.003" target="_blank">https://doi.org/10.1016%2Fj.acha.2012.06.003</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Dhillon, Inderjit Singh (1997). A New O(n2) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem (PDF) (PhD). University of California, Berkeley. p. 8. CSD-97-971, ADA637073. <a href="http://www.cs.utexas.edu/~inderjit/public_papers/thesis.pdf" target="_blank">http://www.cs.utexas.edu/~inderjit/public_papers/thesis.pdf</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Kreer, M. (1994). "Analytic birth-death processes: a Hilbert space approach". Stochastic Processes and Their Applications. 49 (1): 65–74. doi:10.1016/0304-4149(94)90112-0. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Meurant, Gérard (October 2008). "Tridiagonal matrices" (PDF) – via Institute for Computational Mathematics, Hong Kong Baptist University. <a href="http://www.math.hkbu.edu.hk/ICM/LecturesAndSeminars/08OctMaterials/1/Slide3.pdf" target="_blank">http://www.math.hkbu.edu.hk/ICM/LecturesAndSeminars/08OctMaterials/1/Slide3.pdf</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Kreer, M. (1994). "Analytic birth-death processes: a Hilbert space approach". Stochastic Processes and Their Applications. 49 (1): 65–74. doi:10.1016/0304-4149(94)90112-0. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Eidelman, Yuli; Gohberg, Israel; Gemignani, Luca (2007-01-01). "On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms". Linear Algebra and Its Applications. 420 (1): 86–101. doi:10.1016/j.laa.2006.06.028. ISSN 0024-3795. <a href="https://doi.org/10.1016%2Fj.laa.2006.06.028" target="_blank">https://doi.org/10.1016%2Fj.laa.2006.06.028</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> </ol>