# What Is a Symmetric Indefinite Matrix?

A symmetric indefinite matrix $A$ is a symmetric matrix for which the quadratic form $x^TAx$ takes both positive and negative values. By contrast, for a positive definite matrix $x^TAx > 0$ for all nonzero $x$ and for a negative definite matrix $x^TAx < 0$ for all nonzero $x$.

A neat way to express the indefinitess is that there exist vectors $x$ and $y$ for which $(x^TAx)(y^TAy) < 0$.

A symmetric indefinite matrix has both positive and negative eigenvalues and in some sense is a typical symmetric matrix. For example, a random symmetric matrix is usually indefinite:

>> rng(3); B = rand(4); A = B + B'; eig(A)'
ans =
-8.9486e-01  -6.8664e-02   1.1795e+00   3.9197e+00

In general it is difficult to tell if a symmetric matrix is indefinite or definite, but there is one easy-to-spot sufficient condition for indefinitess: if the matrix has a zero diagonal element that has a nonzero element in its row then it is indefinite. Indeed if $a_{kk} = 0$ then $e_k^TAe_k = a_{kk} = 0$, where $e_k$ is the $k$th unit vector, so $A$ cannot be positive definite or negative definite. The existence of a nonzero element in the row of the zero rules out the matrix being positive semidefinite ($x^TAx \ge 0$ for all $x$) or negative semidefinite ($x^TAx \le 0$ for all $x$).

An example of a symmetric indefinite matrix is a saddle point matrix, which has the block $2\times 2$ form

$\notag C = \begin{bmatrix} A & B^T \\ B & 0 \end{bmatrix},$

where $A$ is symmetric positive definite and $B\ne0$. When $A$ is the identity matrix, $C$ is the augmented system matrix associated with a least squares problem $\min_x \|Bx - d\|_2$. Another example is the $n\times n$ reverse identity matrix $J_n$, illustrated by

$\notag J_4 = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix},$

which has eigenvalues $\pm1$ (exercise: how many $1$s and how many $-1$s?). A third example is a Toeplitz tridiagonal matrix with zero diagonal:

>> A = full(gallery('tridiag',5,1,0,1)), eig(sym(A))'
A =
0     1     0     0     0
1     0     1     0     0
0     1     0     1     0
0     0     1     0     1
0     0     0     1     0
ans =
[-1, 0, 1, 3^(1/2), -3^(1/2)]

How can we exploit symmetry in solving a linear system $Ax = b$ with a symmetric indefinite matrix $A$? A Cholesky factorization does not exist, but we could try to compute a factorization $A = LDL^T$, where $L$ is unit lower triangular and $D$ is diagonal with both positive and negative diagonal entries. However, this factorization does not always exist and if it does, its computation in floating-point arithmetic can be numerically unstable. The simplest example of nonexistence is the matrix

$\notag \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix} \ne \begin{bmatrix} 1 & 0 \\ \ell_{21} & 0 \end{bmatrix} \begin{bmatrix} d_{11} & 0 \\ 0 & d_{22}\end{bmatrix} \begin{bmatrix} 1 & \ell_{21}\\ 0 & 1\end{bmatrix}.$

The way round this is to allow $D$ to have $2 \times 2$ blocks. We can compute a block $\mathrm{LDL^T}$ factorization $PAP^T = LDL^T$, were $P$ is a permutation matrix, $L$ is unit lower triangular, and $D$ is block diagonal with diagonal blocks of size $1$ or $2$. Various pivoting strategies, which determine $P$, are possible, but the recommend one is the symmetric rook pivoting strategy of Ashcraft, Grimes, and Lewis (1998), which has the key property of producing a bounded $L$ factor. Solving $Ax = b$ now reduces to substitutions with $L$ and a solve with $D$, which involves solving $2\times 2$ linear systems for the $2\times 2$ blocks and doing divisions for the $1\times 1$ blocks (scalars).

MATLAB implements $\mathrm{LDL^T}$ factorization in its ldl function. Here is an example using Anymatrix:

>> A = anymatrix('core/blockhouse',4), [L,D,P] = ldl(A), eigA = eig(A)'
A =
-4.0000e-01  -8.0000e-01  -2.0000e-01   4.0000e-01
-8.0000e-01   4.0000e-01  -4.0000e-01  -2.0000e-01
-2.0000e-01  -4.0000e-01   4.0000e-01  -8.0000e-01
4.0000e-01  -2.0000e-01  -8.0000e-01  -4.0000e-01
L =
1.0000e+00            0            0            0
0   1.0000e+00            0            0
5.0000e-01  -8.3267e-17   1.0000e+00            0
-2.2204e-16  -5.0000e-01            0   1.0000e+00
D =
-4.0000e-01  -8.0000e-01            0            0
-8.0000e-01   4.0000e-01            0            0
0            0   5.0000e-01  -1.0000e+00
0            0  -1.0000e+00  -5.0000e-01
P =
1     0     0     0
0     1     0     0
0     0     1     0
0     0     0     1
eigA =
-1.0000e+00  -1.0000e+00   1.0000e+00   1.0000e+00

Notice the $2\times 2$ blocks on the diagonal of $D$, each of which contains one negative eigenvalue and one positive eigenvalue. The eigenvalues of $D$ are not the same as those of $A$, but since $A$ and $D$ are congruent they have the same number of positive, zero, and negative eigenvalues.