= Zero-pivot failure of tridiagonal elimination
{title2=$\det\begin{pmatrix}0&1\\1&1\end{pmatrix}=-1$}
An <invertible matrix> need not admit the unpivoted <Thomas algorithm>. For example,
$$
A=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad d=\begin{pmatrix}2\\3\end{pmatrix},\qquad x=\begin{pmatrix}1\\2\end{pmatrix}.
$$
Here $\det A=-1$ and $Ax=d$, but $p_1=0$ makes $m_2=1/0$ undefined. Interchanging the two equations instead gives the upper <triangular matrix> system $x_1+x_2=3$, $x_2=2$, solved immediately by <back substitution>. Even a nonzero first diagonal does not guarantee all later <pivot elements>: $\begin{pmatrix}1&1&0\\1&1&1\\0&1&1\end{pmatrix}$ has <determinant> $-1$, yet $p_2=1-1=0$.
For a general <tridiagonal matrix>, use a solver with <partial pivoting> when these structural guarantees are unavailable or a dangerously small <pivot element> occurs. Adjacent row interchanges can introduce a second upper diagonal, so a pivoted solver must track that additional <fill-in>; it cannot blindly continue the unpivoted <recurrence relations>. LAPACK's `DGTSV` explicitly performs <partial pivoting>, stores this extra upper diagonal, and includes it in <back substitution>. Its fixed-width storage and bounded work per row retain $O(n)$ time for one right-hand side and $O(n)$ storage.<DGTSV (LAPACK 3.12.1) by LAPACK project>[DGTSV, Purpose lines 34–39; DL argument lines 63–69; adjacent interchange lines 188–199; back solve lines 295–305]{ref}
Back to article page
