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 kth 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 1s and how many -1s?). 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.


Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s