{
  "id": "enwiki-001351245241",
  "slug": "tridiagonal-matrix",
  "title": "Tridiagonal matrix",
  "qid": "",
  "lead": "In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal (the first diagonal below this), and the supradiagonal/upper diagonal (the first diagonal above the main diagonal). For example, the following matrix is tridiagonal: : \\begin{pmatrix} 1 & 4 & 0 & 0 \\\\ 3 & 4 & 1 & 0 \\\\ 0 & 2 & 3 & 4 \\\\ 0 & 0 & 1 & 3 \\\\ \\end{pmatrix}. The determinant of a tridiagonal matrix is given by the continuant of its elements. An orthogonal transformation of a symmetric (or Hermitian) matrix to tridiagonal form can be done with the Lanczos algorithm.",
  "body": "In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal (the first diagonal below this), and the supradiagonal/upper diagonal (the first diagonal above the main diagonal). For example, the following matrix is tridiagonal: \\begin{pmatrix} 1 & 4 & 0 & 0 \\\\ 3 & 4 & 1 & 0 \\\\ 0 & 2 & 3 & 4 \\\\ 0 & 0 & 1 & 3 \\\\ \\end{pmatrix}. The determinant of a tridiagonal matrix is given by the continuant of its elements. An orthogonal transformation of a symmetric (or Hermitian) matrix to tridiagonal form can be done with the Lanczos algorithm. ==Properties== A tridiagonal matrix is a matrix that is both upper and lower Hessenberg matrix. In particular, a tridiagonal matrix is a direct sum of p 1-by-1 and q 2-by-2 matrices such that — the dimension of the tridiagonal. Although a general tridiagonal matrix is not necessarily symmetric or Hermitian, many of those that arise when solving linear algebra problems have one of these properties. Furthermore, if a real tridiagonal matrix A satisfies a k,k+1 a k+1,k > 0 for all k, so that the signs of its entries are symmetric, then it is similar to a Hermitian matrix, by a diagonal change of basis matrix. Hence, its eigenvalues are real. If we replace the strict inequality by a k,k+1 a k+1,k &ge; 0, then by continuity, the eigenvalues are still guaranteed to be real, but the matrix need no longer be similar to a Hermitian matrix. The set of all n &times; n tridiagonal matrices forms a 3n-2 dimensional vector space. Many linear algebra algorithms require significantly less computational effort when applied to diagonal matrices, and this improvement often carries over to tridiagonal matrices as well. ===Determinant=== The determinant of a tridiagonal matrix A of order n can be computed from a three-term recurrence relation. Write f 1 &nbsp;=&nbsp;|a 1 |&nbsp;=&nbsp;a 1 (i.e., f 1 is the determinant of the 1 by 1 matrix consisting only of a 1 ), and let 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}. The sequence (f i ) is called the continuant and satisfies the recurrence relation f_n = a_n f_{n-1} - c_{n-1}b_{n-1}f_{n-2} with initial values f 0 &nbsp;=&nbsp;1 and f −1 &nbsp;=&nbsp;0. The cost of computing the determinant of a tridiagonal matrix using this formula is linear in n, while the cost is cubic for a general matrix. ===Inversion=== The inverse of a non-singular tridiagonal matrix T 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} is given by (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\\\\ \\end{cases} where the θ i satisfy the recurrence relation \\theta_i = a_i \\theta_{i-1} - b_{i-1}c_{i-1}\\theta_{i-2} \\qquad i=2,3,\\ldots,n with initial conditions θ 0 &nbsp;=&nbsp;1, θ 1 &nbsp;=&nbsp;a 1 and the ϕ i satisfy \\phi_i = a_i \\phi_{i+1} - b_i c_i \\phi_{i+2} \\qquad i=n-1,\\ldots,1 with initial conditions ϕ n+1 &nbsp;=&nbsp;1 and ϕ n &nbsp;=&nbsp;a n . Closed form solutions can be computed for special cases such as symmetric matrices with all diagonal and off-diagonal elements equal or Toeplitz matrices and for the general case as well. In general, the inverse of a tridiagonal matrix is a semiseparable matrix and vice versa. The inverse of a symmetric tridiagonal matrix can be written as a single-pair matrix (a.k.a. generator-representable semiseparable matrix) of the form \\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} b_i = \\frac{\\beta_1 \\cdots \\beta_{i-1}}{d_1 \\cdots d_i}\\end{cases} with \\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} ===Solution of linear system=== A system of equations Ax&nbsp;=&nbsp;b for&nbsp; b\\in \\R^n can be solved by an efficient form of Gaussian elimination when A is tridiagonal called tridiagonal matrix algorithm, requiring O(n) operations. ===Eigenvalues=== When a tridiagonal matrix is also Toeplitz, there is a simple closed-form solution for its eigenvalues, namely: a - 2 \\sqrt{bc} \\cos \\left (\\frac{k\\pi}{n+1} \\right ), \\qquad k=1, \\ldots, n. A real symmetric tridiagonal matrix has real eigenvalues, and all the eigenvalues are distinct (simple) if all off-diagonal elements are nonzero. 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) operations for a matrix of size n\\times n , although fast algorithms exist which (without parallel computation) require only O(n\\log n) . As a side note, an unreduced 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. 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} where b_i \\neq c_i . Assume that each product of off-diagonal entries is positive b_i c_i > 0 and define a transformation matrix D by 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} The similarity transformation D^{-1} T D yields a symmetric tridiagonal matrix J by: J:=D^{-1} T D = \\begin{pmatrix} a_1 & \\sgn b_1 \\, \\sqrt{b_1 c_1} \\\\ \\sgn b_1 \\, \\sqrt{b_1 c_1} & a_2 & \\sgn b_2 \\, \\sqrt{b_2 c_2} \\\\ & \\sgn b_2 \\, \\sqrt{b_2 c_2} & \\ddots & \\ddots \\\\ & & \\ddots & \\ddots & \\sgn b_{n-1} \\, \\sqrt{b_{n-1} c_{n-1}} \\\\ & & & \\sgn b_{n-1} \\, \\sqrt{b_{n-1} c_{n-1}} & a_n \\end{pmatrix} \\,. Note that T and J have the same eigenvalues. ==Computer programming== A transformation that reduces a general matrix to Hessenberg form will reduce a Hermitian matrix to tridiagonal form. So, many eigenvalue algorithms, when applied to a Hermitian matrix, reduce the input Hermitian matrix to (symmetric real) tridiagonal form as a first step. A tridiagonal matrix can also be stored more efficiently than a general matrix by using a special storage scheme. For instance, the LAPACK Fortran package stores an unsymmetric tridiagonal matrix of order n in three one-dimensional arrays, one of length n containing the diagonal elements, and two of length n &minus; 1 containing the subdiagonal and superdiagonal elements. ==Applications== The discretization in space of the one-dimensional diffusion or heat equation \\frac{\\partial u(t,x)}{\\partial t} = \\alpha \\frac{\\partial^2 u(t,x)}{\\partial x^2} using second order central finite differences results in \\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} with discretization constant \\Delta x . The matrix is tridiagonal with a_{i}=-2 and b_{i}=c_{i}=1 . Note: no boundary conditions were explicitly assigned, but this matrix happens to correspond to Neumann boundary conditions (zero gradient). ==See also== Pentadiagonal matrix Jacobi matrix (operator) ==Notes== ==External links== Tridiagonal and Bidiagonal Matrices in the LAPACK manual. High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form Tridiagonal linear system solver in C++",
  "categories": [
    "23118434",
    "23603337",
    "26709326",
    "48128016"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1351245241",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1777230056.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001351245241",
    "type": "webpage",
    "title": "Tridiagonal matrix",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/tridiagonal-matrix",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001351245241",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1351245241",
    "note": "Immutable snapshot enwiki-001351245241"
  }
}