What Is a Symmetric Indefinite Matrix?
source link: https://nhigham.com/2022/10/25/what-is-a-symmetric-indefinite-matrix/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
What Is a Symmetric Indefinite Matrix?
A symmetric indefinite matrix is a symmetric matrix for which the quadratic form takes both positive and negative values. By contrast, for a positive definite matrix for all nonzero and for a negative definite matrix for all nonzero .
A neat way to express the indefinitess is that there exist vectors and for which .
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 then , where is the th unit vector, so 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 ( for all ) or negative semidefinite ( for all ).
An example of a symmetric indefinite matrix is a saddle point matrix, which has the block form
where is symmetric positive definite and . When is the identity matrix, is the augmented system matrix associated with a least squares problem . Another example is the reverse identity matrix , illustrated by
which has eigenvalues (exercise: how many s and how many 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 with a symmetric indefinite matrix ? A Cholesky factorization does not exist, but we could try to compute a factorization , where is unit lower triangular and 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
The way round this is to allow to have blocks. We can compute a block factorization , were is a permutation matrix, is unit lower triangular, and is block diagonal with diagonal blocks of size or . Various pivoting strategies, which determine , 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 factor. Solving now reduces to substitutions with and a solve with , which involves solving linear systems for the blocks and doing divisions for the blocks (scalars).
MATLAB implements 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 blocks on the diagonal of , each of which contains one negative eigenvalue and one positive eigenvalue. The eigenvalues of are not the same as those of , but since and are congruent they have the same number of positive, zero, and negative eigenvalues.
References
- Cleve Ashcraft, Roger Grimes, and John Lewis, Accurate Symmetric Indefinite Linear Equation Solvers, SIAM J. Matrix Anal. Appl. 20, 513–561, 1998.
- Nicholas J. Higham and Mantas Mikaitis, Anymatrix: An Extendable MATLAB Matrix Collection, Numer. Algorithms, 90:3, 1175–1196, 2021.
Posted on October 25, 2022October 25, 2022 by Nick HighamPosted in what-is
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK