LU decomposition of SPD matrix without partial pivoting?

Question

I get why diagonal dominant matrices do not need partial pivoting before Gaussian elimination can be applied in order to gain a LU decomposition, but why is this also the case for SPD matrices in general?

Answer 1

The general condition for LU to be computable without partial pivoting is that the given matrix $A$ is so called strongly regular, i.e., it has to satisfy $$ det(A_i) \neq 0 \quad \forall i$$ where $A_i$ denotes the $i$-th principal leading submatrix. Easily (by computing first few rows of the Gaussian elimination) you can indeed see that the above condition is equivalent with the fact that the pivots are nonzero at every step. Using the Sylvester's criterion for SPD matrices, you see that the above condition is always met for SPD matrices.

If you were interested in the computational point of view the reasoning is originally due to Wilkinson (see, e.g., the recent book by Higham for detailed reasoning and proofs), who proved that even in the finite precision arithmetics (FPA), the above holds. By this I mean that even in FPA the pivots are not too small relative to the rest of the current row/column of the matrix so that division by those pivots would bring massive instabilities.

Answer 2

Symmetric positive definite matrices can use the Cholesky decomposition however if they are rank deficient then you can use the pivoted Cholesky decomposition. . In general if a matrix $A \in \mathbb{R}^{n \times n}$ is symmetric positive definite then we have the cholesky decomposition so we can write

$$ A = LL^{T} \tag{1} $$

where $L$ is a lower triangular matrix. If $A \in \mathbb{R}^{n \times n}$ is symmetric postive definite of rank $ m < n$ then there exists a permutation matrix $P \in \mathbb{R}^{n \times n}$ such that

$$ P^{T}AP = LL^{T} \tag{2} $$