# What Is the Second Difference Matrix?

The second difference matrix is the tridiagonal matrix $T_n$ with diagonal elements $2$ and sub- and superdiagonal elements $-1$:

$\notag T_n = \left[ \begin{array}{@{}*{4}{r@{\mskip10mu}}r} 2 & -1 & & & \\ -1 & 2 & -1 & & \\[-5pt] & -1 & 2 & \ddots & \\ & & \ddots & \ddots & -1 \\ & & & -1 & 2 \end{array}\right] \in\mathbb{R}^{n\times n}.$

It arises when a second derivative is approximated by the central second difference $f''(x) \approx (f(x+h) -2 f(x) + f(x-h))/h^2$. (Accordingly, the second difference matrix is sometimes defined as $-T_n$.) In MATLAB, $T_n$ can be generated by gallery('tridiag',n), which is returned as a aparse matrix.

This is Gil Strang’s favorite matrix. The photo, from his home page, shows a birthday cake representation of the matrix.

The second difference matrix is symmetric positive definite. The easiest way to see this is to define the full rank rectangular matrix

$\notag L_n = \begin{bmatrix} 1 & & & \\ -1 & 1 & & \\ & -1 & \ddots & \\ & & \ddots & 1 \\ & & & -1 \end{bmatrix} \in\mathbb{R}^{(n+1)\times n}$

and note that $T_n = L_n^T L_n$. The factorization corresponds to representing a central difference as the product of a forward difference and a backward difference. Other properties of the second difference matrix are that it is diagonally dominant, a Toeplitz matrix, and an $M$-matrix.

## Cholesky Factorization

In an LU factorization $A = LU$ the pivots $u_{ii}$ are $2$, $3/2$, $4/3$, …, $(n+1)/n$. Hence the pivots form a decreasing sequence tending to 1 as $n\to\infty$. The diagonal of the Cholesky factor contains the square roots of the pivots. This means that in the Cholesky factorization $A = R^*R$ with $R$ upper bidiagonal, $r_{nn} \to 1$ and $r_{n,n-1}\to -1$ as $n\to\infty$.

## Determinant, Inverse, Condition Number

Since the determinant is the product of the pivots, $\det(T_n) = n+1$.

The inverse of $T_n$ is full, with $(i,j)$ element $i(n-j+1)/(n+1)$ for $j\ge i$. For example,

$\notag T_5^{-1} = \displaystyle\frac{1}{6} \begin{bmatrix} 5 & 4 & 3 & 2 & 1\\ 4 & 8 & 6 & 4 & 2\\ 3 & 6 & 9 & 6 & 3\\ 2 & 4 & 6 & 8 & 4\\ 1 & 2 & 3 & 4 & 5 \end{bmatrix}.$

The $2$-norm condition number satisfies $\kappa_2(T_n) \sim 4n^2/\pi^2$ (as follows from the formula (1) below for the eigenvalues).

## Eigenvalues and Eigenvectors

The eigenvalues of $T_n$ are

$\notag \mu_k = 2 - 2 \cos( k \phi) = 4 \sin^2\Bigl(\displaystyle\frac{k \phi}{2} \Bigr), \quad k = 1:n, \qquad (1)$

where $\phi = \pi/(n+1)$, with corresponding eigenvector

$\notag v_k = \begin{bmatrix} \sin(k\phi), &\sin(2k\phi), &\dots, &\sin(nk\phi) \end{bmatrix}^T.$

The matrix $Q$ with

$\notag q_{ij} = \Bigl(\displaystyle\frac{2}{n+1}\Bigr)^{1/2} \sin\Bigl( \frac{ij\pi}{n+1} \Bigr)$

is therefore an eigenvector matrix for $T_n$: $Q^*AQ = \mathrm{diag}(\mu_k)$.

## Variations

Various modifications of the second difference matrix arise and similar results can be derived. For example, consider the matrix obtained by changing the $(n,n)$ element to $1$:

$\notag \widetilde{T}_n = \left[ \begin{array}{@{}*{4}{r@{\mskip10mu}}r} 2 & -1 & & & \\ -1 & 2 & -1 & & \\[-5pt] & -1 & 2 & \ddots & \\ & & \ddots & \ddots & -1 \\ & & & -1 & 1 \end{array}\right] \in\mathbb{R}^{n\times n}.$

It can be shown that $\widetilde{T}_n^{-1}$ has $(i,j)$ element $\min(i,j)$ and eigenvalues $4\cos( j \pi/(2n+1))^2$, $j=1:n$.

If we perturb the $(1,1)$ of $\widetilde{T}_n$ to $1$, we obtain a singular matrix, but suppose we perturb the $(1,1)$ element to $3$:

$\notag \widehat{T}_n = \left[ \begin{array}{@{}*{4}{r@{\mskip10mu}}r} 3 & -1 & & & \\ -1 & 2 & -1 & & \\[-5pt] & -1 & 2 & \ddots & \\ & & \ddots & \ddots & -1 \\ & & & -1 & 1 \end{array}\right] \in\mathbb{R}^{n\times n}.$

The inverse is $\widehat{T}_n^{-1} = G/2$, where $G$ with $(i,j)$ element $2\min(i,j)-1$ is a matrix of Givens, and the eigenvalues are $4\cos((2j-1)\pi/(4n))^2$, $j=1:n$.

## Notes

The factorization $T_n = L_n^TL_n$ is noted by Strang (2012).

For a derivation of the eigenvalues and eigenvectors see Todd (1977, p. 155 ff.). For the eigenvalues of $\widetilde{T}_n$ see Fortiana and Cuadras (1997). Givens’s matrix is described by Newman and Todd (1958) and Todd (1977).

## References

This is a minimal set of references, which contain further useful references within.