# Diagonally Perturbing a Symmetric Matrix to Make It Positive Definite

Suppose $A$ is a matrix that is symmetric but not positive definite. What is the best way to perturb the diagonal to make $A$ positive definite? We want to compute a vector $d$ such that

$\notag A(d) = A + D, \quad D = \mathrm{diag}(d),$

is positive definite. Since the positive definite matrices form an open set there is no minimal $d$, so we relax the requirement to be that $A$ is positive semidefinite. The perturbation $D$ needs to make any negative eigenvalues of $A$ become nonnegative. We will require all the entries of $d$ to be nonnegative. Denote the eigenvalues of $A$ by $\lambda_n(A) \le \lambda_{n-1}(A) \le \cdots \le \lambda_1(A)$ and assume that $\lambda_n(A) < 0$.

A natural choice is to take $D$ to be a multiple of the identity matrix. For $d_i \equiv \delta$, $A(d)$ has eigenvalues $\lambda_i + \delta$, and so the smallest possible $\delta$ is $\delta = - \lambda_n(A)$. This choice of $D$ shifts all the diagonal elements by the same amount, which might be undesirable for a matrix with widely varying diagonal elements.

When the diagonal entries of $A$ are positive another possibility is to take $d_i = \alpha a_{ii}$, so that each diagonal entry undergoes a relative perturbation of size $\alpha$. Write $D_A = \mathrm{diag}(a_{ii})$ and note that $C = D_A^{-1/2}A D_A^{-1/2}$ is symmetric with unit diagonal. Then

$\notag A + \alpha D_A = D_A^{1/2}(C + \alpha I)D_A^{1/2}.$

Since $A + \alpha D_A$ is positive semidefinite if and only if $C + \alpha I$ is positive semidefinite, the smallest possible $\alpha$ is $\alpha = -\lambda_n(C)$.

More generally, we can treat the $d_i$ as $n$ independent variables and ask for the solution of the optimization problem

$\notag \min \|d\| ~~\mathrm{subject~to}~~ A + \mathrm{diag}(d) ~\mathrm{positive~semidefinite}, ~d \ge 0. \qquad(\dagger)$

Of particular interest are the norms $\|d\|_1 = \sum_i d_i = \mathrm{trace}(D)$ (since $d\ge0)$ and $\|d\|_\infty = \max_i d_i$.

If $A+D$ is positive semidefinite then from standard eigenvalue inequalities,

$\notag 0 \le \lambda_n(A+D) \le \lambda_n(A) + \lambda_1(D),$

so that

$\notag \max_i d_i \ge -\lambda_n(A).$

Since $d_i \equiv -\lambda_n(A)$ satisfies the constraints of $(\dagger)$, this means that this $d$ solves $(\dagger)$ for the $\infty$-norm, though the solution is obviously not unique in general.

For the $1$– and $2$-norms, $(\dagger)$ does not have an explicit solution, but it can be solved by semidefinite programming techniques.

Another approach to finding a suitable $D$ is to compute a modified Cholesky factorization. Given a symmetric $A$, such a method computes a perturbation $E$ such that $A + E = R^TR$ for an upper triangular $R$ with positive diagonal elements, so that $A + E$ is positive definite. The methods of Gill, Murray, and Wright (1981) and Schnabel and Eskow (1990) compute a diagonal $E$. The cost in flops is essentially the same as that of computing a Cholesky factorization ($n^3/3$) flops), so this approach is likely to require fewer flops than computing the minimum eigenvalue or solving an optimization problem, but the perturbations produces will not be optimal.

## Example

We take the $5\times 5$ Fiedler matrix

>> A = gallery('fiedler',5)
A =
0     1     2     3     4
1     0     1     2     3
2     1     0     1     2
3     2     1     0     1
4     3     2     1     0


The smallest eigenvalue is $-5.2361$, so $A+D$ is positive semidefinite for $D_1 = 5.2361I$. The Gill–Murray–Wright method gives $D_{\mathrm{GMW}}$ with diagonal elements

2.0000e+01   4.6159e+00   1.3194e+00   2.5327e+00   1.0600e+01


and has $\lambda_5(A+D_{\mathrm{GMW}}) = 0.5196$ while the Schnabel–Eskow method gives $D_{\mathrm{SE}}$ with diagonal elements

6     6     6     6     6


and has $\lambda_5(A+D_{\mathrm{SE}}) = 0.7639$. If we increase the diagonal elements of $D_1$ by 0.5 to give comparable smallest eigenvalues for the perturbed matrices then we have

$\Vert d\Vert_{\infty}$ $\Vert d \Vert_1$
Shift 5.2361 26.180
Gill-Murray-Wright 20.000 39.068
Schnabel–Eskow 6.000 30.000