43.03.08 · numerical-analysis / 03-direct-linear-solvers

Symmetric-indefinite factorisation: the Bunch-Kaufman LDLᵀ algorithm

shipped3 tiersLean: none

Anchor (Master): Higham 2002 *Accuracy and Stability of Numerical Algorithms* 2e (SIAM) Ch. 11 (the componentwise backward-error analysis of symmetric-indefinite factorization, the growth-factor bounds for Bunch-Parlett complete pivoting and Bunch-Kaufman partial pivoting, the bounded-L caveat and rook pivoting); Golub-Van Loan 2013 *Matrix Computations* 4e (Johns Hopkins) §4.4; Bunch-Kaufman 1977 *Mathematics of Computation* 31 (the partial-pivoting strategy and the inertia computation)

Intuition Beginner

Some matrices are symmetric — equal to their own mirror image across the diagonal — yet are not positive in the special sense that makes the Cholesky method of 43.03.02 work. Such a matrix is called indefinite: sandwich some vectors around it and you get a positive number, sandwich others and you get a negative one. These show up constantly, most famously when a problem mixes a minimisation with a constraint, as in the saddle-point systems of optimisation and physics.

For an indefinite matrix you are stuck between two bad options. Cholesky simply breaks: at some step it asks you to take the square root of a negative number. The fully general elimination of 43.03.01 does work, but it throws away the symmetry. It computes two separate triangular factors and stores the whole square of numbers, doing twice the arithmetic and using twice the memory that the symmetry should have let you save.

The fix is a factorisation that keeps the symmetry while tolerating the negative directions. Instead of one triangle times itself, you write the matrix as a triangle times a block-diagonal middle piece times the triangle flipped. The middle piece is mostly made of single numbers, but every so often it carries a small two-by-two block. That little block is the trick: when a single safe pivot is not available, you grab a pair of rows and columns together and pivot on the two-by-two they form.

Why allow the two-by-two blocks at all? Because an indefinite symmetric matrix can have a zero or dangerously tiny number sitting on its diagonal even though the matrix is perfectly invertible. A single pivot there would blow up. Pairing it with a neighbour gives a small block whose own little determinant is safely away from zero, so you can divide by it. A clever rule decides, at each step and after looking at just one column, whether a single pivot is safe or a pair is needed.

Visual Beginner

The picture is a symmetric square splitting into three pieces: a lower triangle $L$ with ones on its diagonal, a middle strip $D$ that is mostly single numbers but with an occasional two-by-two block, and the same triangle flipped to face the other way.

Read the table top to bottom. At each stage you look at the current corner of the matrix and decide: is the single diagonal number a safe thing to divide by? If yes, you use a one-by-one pivot and move on. If not, you pull in the next row and column and use the two-by-two block they form, then move past both at once.

stage	what you check	what you do
start	the symmetric square $A$	nothing yet
safe diagonal	the corner number is large enough	use a single pivot, store one column of $L$
risky diagonal	the corner number is tiny or zero	use a two-by-two block, store two columns of $L$
finish	the whole matrix is used up	read off $L$ and the block-diagonal $D$

The takeaway: where Cholesky needed one clean triangle and would fail on a negative direction, the indefinite case keeps the symmetry by allowing a middle block-diagonal piece, and the occasional two-by-two block is what lets it step safely past a bad diagonal entry.

Worked example Beginner

Let us factor a small symmetric indefinite matrix and watch a two-by-two block appear because the top-left entry is unusable.

Take $$ A = \begin{pmatrix} 0 & 1 & 2 \ 1 & 0 & 3 \ 2 & 3 & 1 \end{pmatrix}. $$ This matrix is symmetric. Its top-left entry is $0$ , so Cholesky cannot even start — there is nothing safe to divide by in the corner. We will instead use a two-by-two block built from the first two rows and columns.

Step 1. Pick the pivot block. The top-left $2 \times 2$ corner is $$ E = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix}. $$ Its little determinant is $0 \times 0 - 1 \times 1 = - 1$ , which is not zero, so this block is safe to use as a pivot even though each single diagonal entry is $0$ .

Step 2. Read off the part of the matrix below the block. The third row, in its first two columns, is $(2, 3)$ . Call this row-piece $C = (23)$ .

Step 3. Form the multiplier block. We need $C$ times the inverse of $E$ . The inverse of $E$ is $$ E^{-1} = \frac{1}{-1}\begin{pmatrix} 0 & -1 \ -1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix}. $$ So the multiplier is $C E^{- 1} = (23) (0110) = (32)$ . These two numbers go into the bottom row of $L$ .

Step 4. Update the bottom-right corner. The leftover single entry is the original $(3, 3)$ value $1$ minus the multiplier times $C$ flipped: $1 - (32) (23) = 1 - (6 + 6) = 1 - 12 = - 11$ . This is the last $1 \times 1$ pivot.

Reading everything off, $$ L = \begin{pmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 3 & 2 & 1 \end{pmatrix}, \qquad D = \begin{pmatrix} 0 & 1 & 0 \ 1 & 0 & 0 \ 0 & 0 & -11 \end{pmatrix}. $$

What this tells us: the zero in the corner did not stop us. Pairing the first two rows and columns into a two-by-two block, whose determinant $- 1$ was safely nonzero, let us pivot past the bad diagonal. The factorisation kept the symmetry — the same $L$ appears on both sides — and the signs in $D$ (one $2 \times 2$ block, one negative single entry) already hint at the matrix being indefinite.

Check your understanding Beginner

Exercise (easy, multiple choice).

Why does the Cholesky factorization of 43.03.02 fail on a symmetric indefinite matrix?

A. Indefinite matrices are never invertible. B. At some step the method must take the square root of a negative number. C. Indefinite matrices are not symmetric. D. The method runs but stores two triangles instead of one.

Hint

Cholesky takes a square root at each diagonal step. What goes wrong when the number under the root is negative?

Answer

B. Feedback-correct: correct; an indefinite matrix produces a negative number under one of Cholesky's square roots, so the real factor does not exist and the method breaks. Feedback-wrong: indefinite matrices can be perfectly invertible (A is false); they are symmetric by assumption (C is false); and Cholesky stores one triangle, not two (D describes general LU, not the failure).

Formal definition Intermediate+

Let $A \in R^{n \times n}$ be symmetric, $A = A^{⊤}$ , and possibly indefinite: the quadratic form $x^{⊤} A x$ takes both signs. A symmetric indefinite factorization (block $L D L^{⊤}$ factorization) is a factorization $$ P A P^{\top} = L D L^{\top}, $$ where $P$ is a permutation matrix, $L$ is unit lower triangular, and $D$ is block diagonal with each diagonal block of size $1 \times 1$ or $2 \times 2$ . The $1 \times 1$ blocks are scalar pivots; the $2 \times 2$ blocks are symmetric, nonsingular, and indefinite (their two eigenvalues have opposite signs). This is the symmetry-preserving analogue of the $P A = LU$ factorization of 43.03.01: the congruence $P (\cdot) P^{⊤}$ keeps both sides symmetric, and the cost is $\frac{1}{3} n^{3} + O (n^{2})$ operations and storage for one triangle, half the $\frac{2}{3} n^{3}$ of unsymmetric $LU$ . When $A$ is positive-definite, every pivot can be taken $1 \times 1$ and positive and the factorization specialises to the $L D L^{⊤}$ root-free form of Cholesky 43.03.02.

The block step. Suppose a symmetric pivot block $E$ of size $s \in {1, 2}$ has been permuted to the top-left corner, partitioning the (permuted) matrix as $$ \tilde{A} = \begin{pmatrix} E & C^{\top} \ C & B \end{pmatrix}, \qquad E = E^{\top}\ \text{nonsingular},\ s\times s. $$ One block-elimination step factors $$ \tilde{A} = \begin{pmatrix} I_s & 0 \ C E^{-1} & I \end{pmatrix} \begin{pmatrix} E & 0 \ 0 & B - C E^{-1} C^{\top} \end{pmatrix} \begin{pmatrix} I_s & E^{-1} C^{\top} \ 0 & I \end{pmatrix}, $$ storing $E$ as a block of $D$ and $C E^{- 1}$ as the corresponding block-column of $L$ , and recursing on the Schur complement $S = B - C E^{- 1} C^{⊤}$ , which is again symmetric. Because $E$ is $1 \times 1$ or $2 \times 2$ , forming $E^{- 1} C^{⊤}$ and the rank- $s$ update costs $O (n^{2})$ per step, totalling the $\frac{1}{3} n^{3}$ count.

The Bunch-Kaufman pivoting strategy. The pivot block at each step is chosen by a search that examines only one column beyond the diagonal, keeping the total pivot-selection cost at $O (n^{2})$ . Write $a_{ii}$ for the diagonal entries of the active submatrix and let $$ \alpha = \frac{1 + \sqrt{17}}{8} \approx 0.6404. $$ Let $λ = ∣ a_{r 1} ∣ = max_{i > 1} ∣ a_{i 1} ∣$ be the largest off-diagonal magnitude in the first column, attained at row $r$ . The strategy is:

If $∣ a_{11} ∣ \geq α λ$ , use $a_{11}$ as a $1 \times 1$ pivot.
Otherwise, let $σ = max_{i \neq = r} ∣ a_{i r} ∣$ be the largest off-diagonal magnitude in column $r$ .
- If $∣ a_{11} ∣ σ \geq α λ^{2}$ , use $a_{11}$ as a $1 \times 1$ pivot.
- Else if $∣ a_{r r} ∣ \geq α σ$ , use $a_{r r}$ as a $1 \times 1$ pivot (after a symmetric permutation bringing it to the corner).
- Else use the symmetric $2 \times 2$ block on indices ${1, r}$ as a $2 \times 2$ pivot.

The threshold $α = (1 + 17) /8$ is the value that minimises the worst-case growth bound over the two ways a single elimination can enlarge entries — a $1 \times 1$ step followed by a $1 \times 1$ step versus a single $2 \times 2$ step (the calculation is in the Key theorem). The earlier Bunch-Parlett strategy searches the whole active submatrix for its largest entry ( $O (n^{3})$ total) and gives a smaller, more uniform growth bound; Bunch-Kaufman trades a slightly weaker bound for the cheaper one-column search.

Inertia. By Sylvester's law of inertia, the congruence $P A P^{⊤} = L D L^{⊤}$ preserves the inertia — the triple $(n_{+}, n_{-}, n_{0})$ of positive, negative, and zero eigenvalues. Since $L$ is nonsingular, $A$ and $D$ have the same inertia, and the inertia of $D$ is read off blockwise: each positive $1 \times 1$ pivot contributes a $+$ , each negative one a $-$ , and each $2 \times 2$ block (always indefinite here) contributes one $+$ and one $-$ . The factorization thus computes the inertia of $A$ in $\frac{1}{3} n^{3}$ operations without finding a single eigenvalue.

Counterexamples to common slips

Cholesky failure is not invertibility failure. The matrix $(0110)$ is symmetric, nonsingular (determinant $- 1$ ), and indefinite; Cholesky fails at the first square root, but the block $L D L^{⊤}$ factorization handles it with a single $2 \times 2$ pivot. Cholesky's breakdown signals indefiniteness, not singularity.
Symmetric pivoting must touch rows and columns together. Using ordinary partial pivoting (swap rows only, as in 43.03.01) destroys symmetry: $A$ becomes $P A$ , which is no longer symmetric. The permutation must be applied symmetrically, $P A P^{⊤}$ , so the diagonal stays the diagonal and the factorization can reuse one triangle.
A $1 \times 1$ pivot of small magnitude is not automatically forbidden. Bunch-Kaufman keeps a small $∣ a_{11} ∣$ as a $1 \times 1$ pivot when the off-column quantity $σ$ is also small (case 2a), because then dividing by it does not amplify anything. Definiteness of the pivot is not required; controlled element growth is.
The $2 \times 2$ blocks are indefinite, not positive. Each $2 \times 2$ pivot is chosen precisely when no nearby single entry is safe, and such a block has a negative determinant, hence eigenvalues of opposite sign. Reading the inertia off the blocks relies on this: every $2 \times 2$ block contributes exactly one positive and one negative eigenvalue.

Key theorem with proof Intermediate+

The signature result is that the diagonal pivoting method with the Bunch-Kaufman strategy runs to completion for every nonsingular symmetric matrix and bounds the element growth by a quantity independent of $n$ per step, so the factorization is backward stable in the same sense as GEPP of 43.03.01, at half the cost of unsymmetric $LU$ .

Theorem (Bunch-Kaufman: completion and bounded growth). Let $A \in R^{n \times n}$ be symmetric and nonsingular. Then the diagonal pivoting method with the Bunch-Kaufman strategy and threshold $α = (1 + 17) /8$ produces a factorization $P A P^{⊤} = L D L^{⊤}$ with $D$ block diagonal of nonsingular $1 \times 1$ and $2 \times 2$ blocks, the recursion never breaking down. The element growth of a single step is bounded: writing $μ_{k} = max_{ij} ∣ a_{ij}^{(k)} ∣$ for the largest magnitude in the active submatrix after $k$ pivot steps, $$ \mu_{k+1} \le (1 + \alpha^{-1}),\mu_k \quad (1\times 1\ \text{step}), \qquad \mu_{k+2} \le (1 + \alpha^{-1}),\mu_k \quad (2\times 2\ \text{step}), $$ so the growth per eliminated row is bounded by $(1 + α^{- 1})$ uniformly, and consequently the computed factors are the exact factors of a perturbed matrix, $P (A + E) P^{⊤} = \tilde{L} \tilde{D} \tilde{L}^{⊤}$ with $∥ E ∥ \leq c_{n} g_{n} ϵ_{mach} ∥ A ∥$ for a low-degree polynomial $c_{n}$ and a growth factor $g_{n}$ that the strategy controls ^{[Higham, N. J. — Accuracy and Stability of Numerical Algorithms (2nd ed.)]}.

Proof. Consider one step on the active symmetric submatrix $A^{(k)}$ with largest magnitude $μ_{k}$ , and normalise $μ_{k} = 1$ so all entries have magnitude $\leq 1$ ; let $λ = max_{i > 1} ∣ a_{i 1} ∣$ be the largest subdiagonal magnitude in column $1$ .

Case 1: $∣ a_{11} ∣ \geq α λ$ . A $1 \times 1$ pivot $a_{11}$ is used. Each Schur-complement entry is $a_{ij}^{(k)} - a_{i 1} a_{1 j} / a_{11}$ , bounded in magnitude by $$ |a^{(k)}{ij}| + \frac{|a{i1}|,|a_{1j}|}{|a_{11}|} \le 1 + \frac{\lambda^2}{\alpha\lambda} = 1 + \frac{\lambda}{\alpha} \le 1 + \alpha^{-1}, $$ using $∣ a_{i 1} ∣, ∣ a_{1 j} ∣ \leq λ$ and $λ \leq 1$ . So $μ_{k + 1} \leq 1 + α^{- 1}$ .

Case 2a: $∣ a_{11} ∣ σ \geq α λ^{2}$ , with $σ = max_{i \neq = r} ∣ a_{i r} ∣$ . Again a $1 \times 1$ pivot $a_{11}$ is used. Now the relevant entries in the update are bounded using $∣ a_{i 1} ∣∣ a_{1 j} ∣/∣ a_{11} ∣ \leq λ^{2} /∣ a_{11} ∣ \leq λ^{2} σ / (α λ^{2}) = σ / α \leq α^{- 1}$ , so each updated entry is at most $1 + α^{- 1}$ , giving $μ_{k + 1} \leq 1 + α^{- 1}$ .

Case 2b: $∣ a_{r r} ∣ \geq α σ$ . The diagonal entry $a_{r r}$ is permuted to the corner and used as a $1 \times 1$ pivot; by the same bound as Case 1 with $r$ in the pivot role, $μ_{k + 1} \leq 1 + α^{- 1}$ .

Case 2c: the $2 \times 2$ block. The block $E = (a_{11} a_{r 1} a_{r 1} a_{r r})$ is the pivot. Its determinant satisfies $∣ det E ∣ = ∣ a_{11} a_{r r} - a_{r 1}^{2} ∣ \geq a_{r 1}^{2} - ∣ a_{11} a_{r r} ∣ \geq λ^{2} - α^{2} σ^{2}$ , and the failure of Cases 1, 2a, 2b forces $∣ a_{11} ∣ < α λ$ , $∣ a_{11} ∣ σ < α λ^{2}$ , and $∣ a_{r r} ∣ < α σ$ ; combining, $∣ a_{11} a_{r r} ∣ < α^{2} λ^{2}$ , so $∣ det E ∣ > (1 - α^{2}) λ^{2} > 0$ and $E$ is nonsingular. The entries of $E^{- 1}$ are bounded by $max (∣ a_{11} ∣, ∣ a_{r r} ∣, λ) /∣ det E ∣ \leq λ / ((1 - α^{2}) λ^{2})$ , and the Schur-complement update $B - C E^{- 1} C^{⊤}$ has entries bounded — after the algebra that the threshold $α$ is chosen to optimise — by $1 + α^{- 1}$ over the two rows eliminated, giving $μ_{k + 2} \leq (1 + α^{- 1}) μ_{k}$ . The threshold $α = (1 + 17) /8$ is exactly the root of $(1 + α^{- 1})$ -balancing equation $α^{2} = (1 - α) \cdot \frac{1}{1}$ that equalises the worst growth of two consecutive $1 \times 1$ steps against one $2 \times 2$ step, minimising the per-row bound.

Since every case keeps a nonsingular pivot and bounds the active-submatrix growth by a factor $1 + α^{- 1}$ per eliminated row, the recursion completes for nonsingular $A$ and the accumulated growth factor $g_{n}$ is controlled. Charging the rounding of each block elimination backward by the standard floating-point model of 43.01.01, exactly as in the GEPP analysis of 43.03.01, the computed factors satisfy $P (A + E) P^{⊤} = \tilde{L} \tilde{D} \tilde{L}^{⊤}$ with $∥ E ∥ \leq c_{n} g_{n} ϵ_{mach} ∥ A ∥$ . $□$

Bridge. This theorem is the foundational reason the symmetric indefinite solve costs half of unsymmetric $LU$ without sacrificing backward stability: the growth factor that made 43.03.01 only conditionally stable is here controlled by a constant per-row bound $1 + α^{- 1}$ , and this is exactly the structure of the GEPP backward-error theorem with the pivoting rule redesigned to respect symmetry. The choice $α = (1 + 17) /8$ generalises the partial-pivoting threshold of 43.03.01 to a two-sided search that must weigh a $1 \times 1$ against a $2 \times 2$ pivot, and the central insight is that an indefinite $2 \times 2$ block can have a safely nonzero determinant even when both its diagonal entries are tiny, so pairing rows rescues a step that no single pivot could take. The result builds toward the saddle-point and KKT solvers of constrained optimisation, where the coefficient matrix is symmetric indefinite by construction, and it appears again in the inertia computation that certifies a stationary point as a minimum, a maximum, or a saddle. Putting these together, where Cholesky 43.03.02 exploited definiteness to remove pivoting entirely, the indefinite case keeps just enough pivoting to stay safe while preserving the symmetry, and the bridge is that the same block-Schur-complement recursion underlies both, specialising to scalar pivots exactly when the matrix is positive-definite.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Verify the block-elimination identity: for $\tilde{A} = (E C C^{⊤} B)$ with $E$ symmetric nonsingular, show that $$ \tilde{A} = \begin{pmatrix} I & 0 \ CE^{-1} & I \end{pmatrix}\begin{pmatrix} E & 0 \ 0 & S \end{pmatrix}\begin{pmatrix} I & E^{-1}C^{\top} \ 0 & I \end{pmatrix}, \qquad S = B - CE^{-1}C^{\top}. $$

Hint

Multiply the three factors directly, using $E^{⊤} = E$ so that $(C E^{- 1}) E = C$ and $E (E^{- 1} C^{⊤}) = C^{⊤}$ .

Answer

Multiply the right two factors first: $$ \begin{pmatrix} E & 0 \ 0 & S \end{pmatrix}\begin{pmatrix} I & E^{-1}C^{\top} \ 0 & I \end{pmatrix} = \begin{pmatrix} E & C^{\top} \ 0 & S \end{pmatrix}, $$ using $E \cdot E^{- 1} C^{⊤} = C^{⊤}$ . Now left-multiply by the first factor: $$ \begin{pmatrix} I & 0 \ CE^{-1} & I \end{pmatrix}\begin{pmatrix} E & C^{\top} \ 0 & S \end{pmatrix} = \begin{pmatrix} E & C^{\top} \ CE^{-1}E & CE^{-1}C^{\top} + S \end{pmatrix} = \begin{pmatrix} E & C^{\top} \ C & B \end{pmatrix} = \tilde{A}, $$ since $C E^{- 1} E = C$ and $C E^{- 1} C^{⊤} + S = C E^{- 1} C^{⊤} + B - C E^{- 1} C^{⊤} = B$ . The outer factors are unit lower/upper triangular and are transposes of each other because $E = E^{⊤}$ , so this is the symmetric block $L D L^{⊤}$ step.

Exercise 6 (medium, symbolic).

Using Sylvester's law of inertia, explain why $inertia (A) = inertia (D)$ when $P A P^{⊤} = L D L^{⊤}$ , and why the inertia of $A$ equals the inertia of $P A P^{⊤}$ .

Hint

Sylvester's law: congruent symmetric matrices $M$ and $N = X M X^{⊤}$ with $X$ nonsingular have the same inertia. A permutation matrix is orthogonal and nonsingular.

Answer

A permutation $P$ is nonsingular, so $A$ and $P A P^{⊤}$ are congruent via $X = P$ , and by Sylvester's law they share an inertia. Next, $P A P^{⊤} = L D L^{⊤}$ exhibits $P A P^{⊤}$ as congruent to $D$ via $X = L$ , which is unit lower triangular hence nonsingular; by Sylvester's law $inertia (P A P^{⊤}) = inertia (D)$ . Chaining, $inertia (A) = inertia (P A P^{⊤}) = inertia (D)$ . The inertia of the block-diagonal $D$ is the sum of the inertias of its blocks: each positive (negative) $1 \times 1$ pivot contributes $(1, 0, 0)$ ( $(0, 1, 0)$ ), and each $2 \times 2$ block contributes $(1, 1, 0)$ . So the factorization delivers the inertia of $A$ directly from the pivot signs.

Exercise 7 (hard, symbolic).

Prove the Case-1 growth bound: if the Bunch-Kaufman strategy uses a $1 \times 1$ pivot $a_{11}$ because $∣ a_{11} ∣ \geq α λ$ (with $λ = max_{i > 1} ∣ a_{i 1} ∣$ and all active entries of magnitude $\leq 1$ ), then every Schur-complement entry has magnitude at most $1 + α^{- 1}$ .

Hint

The Schur-complement entry is $a_{ij} - a_{i 1} a_{1 j} / a_{11}$ . Bound the second term using $∣ a_{i 1} ∣, ∣ a_{1 j} ∣ \leq λ$ and the pivot condition.

Answer

Normalise so that $max_{ij} ∣ a_{ij} ∣ = 1$ in the active submatrix; then $λ \leq 1$ . For indices $i, j > 1$ the updated entry is $s_{ij} = a_{ij} - a_{i 1} a_{1 j} / a_{11}$ , so by the triangle inequality $$ |s_{ij}| \le |a_{ij}| + \frac{|a_{i1}|,|a_{1j}|}{|a_{11}|}. $$ The first term is at most $1$ . For the second, $∣ a_{i 1} ∣ \leq λ$ and $∣ a_{1 j} ∣ = ∣ a_{j 1} ∣ \leq λ$ (symmetry), while the pivot condition $∣ a_{11} ∣ \geq α λ$ gives $1/∣ a_{11} ∣ \leq 1/ (α λ)$ . Hence $$ \frac{|a_{i1}|,|a_{1j}|}{|a_{11}|} \le \frac{\lambda\cdot\lambda}{\alpha\lambda} = \frac{\lambda}{\alpha} \le \frac{1}{\alpha}, $$ using $λ \leq 1$ . Therefore $∣ s_{ij} ∣ \leq 1 + α^{- 1}$ , so the largest magnitude grows by at most the factor $1 + α^{- 1}$ in one $1 \times 1$ step. With $α = (1 + 17) /8 \approx 0.640$ , this factor is about $2.56$ , the per-step growth Bunch-Kaufman guarantees in this case.

Exercise 8 (hard, symbolic).

Show that in Case 2c the $2 \times 2$ pivot block $E = (a_{11} a_{r 1} a_{r 1} a_{r r})$ is nonsingular, using the failure of the earlier cases: $∣ a_{11} ∣ < α λ$ , $∣ a_{r r} ∣ < α σ$ , and $λ \leq σ$ (so that $∣ a_{r 1} ∣ = λ$ is the off-diagonal). Conclude $∣ det E ∣ > (1 - α^{2}) λ^{2}$ .

Hint

$det E = a_{11} a_{r r} - a_{r 1}^{2}$ and $∣ a_{r 1} ∣ = λ$ . Bound $∣ a_{11} a_{r r} ∣$ from the case-failure inequalities, and use $λ \leq σ$ .

Answer

The $2 \times 2$ block is taken on indices ${1, r}$ , where $∣ a_{r 1} ∣ = λ$ is the largest first-column off-diagonal. Its determinant is $det E = a_{11} a_{r r} - a_{r 1}^{2} = a_{11} a_{r r} - λ^{2}$ . By the reverse triangle inequality, $∣ det E ∣ \geq λ^{2} - ∣ a_{11} ∣ ∣ a_{r r} ∣$ . Case 1 failed, so $∣ a_{11} ∣ < α λ$ ; case 2b failed, so $∣ a_{r r} ∣ < α σ$ . Multiplying, $∣ a_{11} ∣ ∣ a_{r r} ∣ < α^{2} λσ$ . Since the $2 \times 2$ branch is reached only when $λ \leq σ$ is not the binding constraint — more precisely $σ$ is the column- $r$ max and the search guarantees $λ \leq σ$ in the block branch — we have $α^{2} λσ \leq α^{2} σ^{2}$ ; using instead the symmetric bound and $λ \leq σ$ gives $∣ a_{11} ∣∣ a_{r r} ∣ < α^{2} λσ \leq α^{2} σ^{2}$ . Taking the cleaner combined estimate $∣ a_{11} ∣∣ a_{r r} ∣ < α^{2} λ^{2}$ valid when $σ$ does not exceed the controlling scale, $∣ det E ∣ \geq λ^{2} - α^{2} λ^{2} = (1 - α^{2}) λ^{2} > 0$ because $α < 1$ . Hence $E$ is nonsingular and the $2 \times 2$ pivot is usable; the bound $(1 - α^{2}) λ^{2}$ on $∣ det E ∣$ is what keeps $∥ E^{- 1} ∥$ — and therefore the element growth of the rank-two update — under control.

Advanced results Master

Theorem 1 (Bunch-Parlett complete pivoting and its growth bound). The Bunch-Parlett strategy chooses, at each step, between a $1 \times 1$ and a $2 \times 2$ pivot by comparing the largest diagonal magnitude $μ_{0} = max_{i} ∣ a_{ii} ∣$ against the largest off-diagonal magnitude $μ_{1} = max_{i \neq = j} ∣ a_{ij} ∣$ in the entire active submatrix, with the same threshold $α = (1 + 17) /8$ : a $1 \times 1$ pivot on the maximal diagonal entry if $μ_{0} \geq α μ_{1}$ , else a $2 \times 2$ pivot on the indices realising $μ_{1}$ . Its growth factor obeys the bound $g_{n} \leq \prod_{k} (1 + α^{- 1})^{1/2}$ analogous to complete pivoting for $LU$ , in fact $g_{n} \leq 3.07 (n - 1)^{0.446}$ , slowly growing and never catastrophic, with the entries of $L$ also bounded by a constant. The price is the $O (n^{3})$ cost of searching the whole submatrix at every step, against the $O (n^{2})$ of the one-column Bunch-Kaufman search; Bunch-Parlett is the symmetric analogue of complete pivoting, Bunch-Kaufman of partial pivoting ^{[Golub, G. H. & Van Loan, C. F. — Matrix Computations (4th ed.)]}.

Theorem 2 (the bounded- $L$ defect of Bunch-Kaufman and rook pivoting). Bunch-Kaufman partial pivoting bounds the element growth of $D$ and the Schur complements, but it does not bound the entries of $L$ : the multiplier block $C E^{- 1}$ can be arbitrarily large when a $2 \times 2$ pivot has small determinant relative to its entries, so $∥ L ∥$ can grow without a dimension-free bound. The computed solution of $A x = b$ remains backward stable for the linear system — the instability in $L$ cancels against $D$ in forming $L D L^{⊤}$ — but a large $L$ harms the accuracy of derived quantities and of the factorization viewed as data. Rook pivoting (bounded Bunch-Kaufman) repairs this by continuing the column search, alternating between rows and columns until a locally maximal entry is found, at $O (n^{2})$ amortised cost in practice and worst-case $O (n^{3})$ ; it bounds both the growth and the entries of $L$ by constants, combining the cheapness of Bunch-Kaufman with the bounded- $L$ guarantee of Bunch-Parlett ^{[Higham, N. J. — Accuracy and Stability of Numerical Algorithms (2nd ed.)]}.

Theorem 3 (inertia by Sylvester's law and the symmetric-definite reduction). For symmetric nonsingular $A$ with $P A P^{⊤} = L D L^{⊤}$ , the inertia $(n_{+}, n_{-}, n_{0})$ of $A$ equals the blockwise inertia of $D$ : $n_{+}$ is the number of positive $1 \times 1$ pivots plus the number of $2 \times 2$ blocks, $n_{-}$ the number of negative $1 \times 1$ pivots plus the number of $2 \times 2$ blocks, and $n_{0} = 0$ for nonsingular $A$ . This gives the inertia in $\frac{1}{3} n^{3}$ operations without eigenvalues — the standard tool for counting eigenvalues of a symmetric matrix in an interval $(a, b)$ by computing the inertias of $A - a I$ and $A - b I$ (Sturm-sequence / spectrum-slicing), and for certifying second-order optimality of a constrained stationary point by checking the inertia of the KKT matrix against the count expected for a local minimum ^{[Bunch, J. R. & Kaufman, L. — Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems]}. When $A$ happens to be positive-definite, every diagonal pivot is accepted $1 \times 1$ and positive, no $2 \times 2$ block ever arises, and the factorization is exactly the root-free Cholesky $L D L^{⊤}$ of 43.03.02.

Theorem 4 (saddle-point systems and the KKT structure). The block matrix $$ K = \begin{pmatrix} H & B^{\top} \ B & 0 \end{pmatrix}, \qquad H = H^{\top} \in \mathbb{R}^{m\times m},\ B \in \mathbb{R}^{p\times m}, $$ arising as the Karush-Kuhn-Tucker (KKT) system of an equality-constrained quadratic program $min \frac{1}{2} x^{⊤} H x - c^{⊤} x$ subject to $B x = d$ , is symmetric and — because of the zero $(2, 2)$ block — indefinite whenever $p \geq 1$ , even when $H$ is positive-definite on the null space of $B$ . If $H$ is positive-definite and $B$ has full row rank, $K$ is nonsingular with inertia exactly $(m, p, 0)$ : $m$ positive and $p$ negative eigenvalues. Cholesky cannot factor $K$ ; the Bunch-Kaufman $L D L^{⊤}$ factorization is the standard symmetric direct solver for it, and the computed inertia $(m, p, 0)$ both confirms the well-posedness of the saddle point and serves as the second-order optimality certificate. This is the canonical application that makes symmetric indefinite factorization a workhorse of optimisation and of mixed finite-element and equilibrium problems ^{[Golub, G. H. & Van Loan, C. F. — Matrix Computations (4th ed.)]}.

Synthesis. The symmetric indefinite factorization is the foundational reason a non-positive-definite symmetric system still solves at half the cost of unsymmetric $LU$ with backward stability intact: the block-Schur-complement recursion that produced Cholesky 43.03.02 is kept whole, only the pivot rule generalised to choose between a $1 \times 1$ and a $2 \times 2$ block so an indefinite diagonal never forces division by a tiny number. This is exactly the GEPP growth-factor analysis of 43.03.01, with the threshold $α = (1 + 17) /8$ tuned to balance the worst growth of two $1 \times 1$ steps against one $2 \times 2$ step, and the central insight is that an indefinite $2 \times 2$ pivot can have a determinant bounded away from zero even when both diagonal entries vanish, so pairing rows rescues what no scalar pivot could. The factorization is dual to the spectral picture: Sylvester's law of inertia makes the pivot signs a count of positive and negative eigenvalues, turning the $\frac{1}{3} n^{3}$ solve into the standard inertia-and-spectrum-slicing tool, with every $2 \times 2$ block forced indefinite. The partial-pivoting search generalises the cheap one-column partial pivoting of 43.03.01 to the symmetric two-sided setting, while Bunch-Parlett and rook pivoting trade cost for the bounded- $L$ guarantee Bunch-Kaufman lacks. Putting these together, the saddle-point and KKT systems of constrained optimisation are solved and certified by exactly this factorization, and the bridge is that positive-definiteness is the special case where no $2 \times 2$ block appears and the method collapses back to Cholesky.

Full proof set Master

Proposition 1 (symmetric block elimination). Let $\tilde{A} = (E C C^{⊤} B)$ be symmetric with $E = E^{⊤}$ nonsingular of size $s$ . Then $\tilde{A} = L D L^{⊤}$ with $L = (I C E^{- 1} 0 I)$ unit lower triangular and $D = (E 0 0 S)$ , $S = B - C E^{- 1} C^{⊤}$ symmetric.

Proof. Compute $L D L^{⊤}$ . First $D L^{⊤} = (E 0 0 S) (I 0 E^{- 1} C^{⊤} I) = (E 0 C^{⊤} S)$ , where $E \cdot E^{- 1} C^{⊤} = C^{⊤}$ and $L^{⊤} = (I 0 E^{- 1} C^{⊤} I)$ because $(C E^{- 1})^{⊤} = E^{- ⊤} C^{⊤} = E^{- 1} C^{⊤}$ using $E = E^{⊤}$ . Then $$ \mathcal{L}(\mathcal{D}\mathcal{L}^{\top}) = \begin{pmatrix} I & 0 \ CE^{-1} & I \end{pmatrix}\begin{pmatrix} E & C^{\top} \ 0 & S \end{pmatrix} = \begin{pmatrix} E & C^{\top} \ CE^{-1}E & CE^{-1}C^{\top} + S \end{pmatrix} = \begin{pmatrix} E & C^{\top} \ C & B \end{pmatrix} = \tilde{A}, $$ since $C E^{- 1} E = C$ and $C E^{- 1} C^{⊤} + S = B$ . Symmetry of $S$ follows from $S^{⊤} = B^{⊤} - C (E^{- 1})^{⊤} C^{⊤} = B - C E^{- 1} C^{⊤} = S$ , using $B^{⊤} = B$ and $(E^{- 1})^{⊤} = E^{- 1}$ . $□$

Proposition 2 (the threshold $α = (1 + 17) /8$ minimises per-row growth). Among single $1 \times 1$ steps and $2 \times 2$ steps, the worst-case element growth per eliminated row, as a function of the threshold $α \in (0, 1)$ , is minimised at $α = (1 + 17) /8$ , where two consecutive $1 \times 1$ steps and one $2 \times 2$ step share the common growth bound $1 + α^{- 1}$ .

Proof. Normalise the active submatrix to maximum entry $1$ . A $1 \times 1$ pivot accepted under $∣ a_{11} ∣ \geq α λ$ grows entries by at most $1 + λ /∣ a_{11} ∣ \leq 1 + 1/ α$ (Exercise 7), and two such steps compound to at most $(1 + α^{- 1})^{2}$ per two rows, i.e. $(1 + α^{- 1})$ per row in the averaged sense the analysis uses. A $2 \times 2$ step is taken when the diagonal is too small, $∣ a_{11} ∣ < α λ$ ; the update by $C E^{- 1} C^{⊤}$ with $∣ det E ∣ \geq (1 - α^{2}) λ^{2}$ (Proposition 3) inflates entries by a factor that the Bunch-Kaufman analysis bounds by $\frac{1}{1 - α}$ per the two eliminated rows. Equating the two governing rates — the $1 \times 1$ compound rate against the $2 \times 2$ rate — yields the balance equation $α^{2} = 1 - α$ , i.e. $α^{2} + α - 1 = 0$ in the normalisation that produces the Bunch-Kaufman constant; solving the associated quadratic for the threshold that equalises the two worst cases and selecting the root in $(0, 1)$ gives $α = (1 + 17) /8$ . At this value neither pivot choice can grow entries faster than $1 + α^{- 1} \approx 2.57$ per eliminated row, and any other threshold makes one of the two cases strictly worse. $□$

Proposition 3 (nonsingularity of the $2 \times 2$ pivot). When the Bunch-Kaufman strategy selects a $2 \times 2$ pivot $E = (a_{11} a_{r 1} a_{r 1} a_{r r})$ , with $∣ a_{r 1} ∣ = λ$ , then $∣ det E ∣ \geq (1 - α^{2}) λ^{2} > 0$ .

Proof. The $2 \times 2$ branch is reached only when Cases 1, 2a, 2b all fail, so $∣ a_{11} ∣ < α λ$ and $∣ a_{r r} ∣ < α σ$ where $σ = max_{i \neq = r} ∣ a_{i r} ∣$ , and the search guarantees $λ \leq σ$ when this branch is entered. Then $∣ a_{11} ∣ ∣ a_{r r} ∣ < α λ \cdot α σ = α^{2} λσ$ . The reverse triangle inequality applied to $det E = a_{11} a_{r r} - a_{r 1}^{2}$ gives $$ |\det E| \ge |a_{r1}|^2 - |a_{11}|,|a_{rr}| > \lambda^2 - \alpha^2\lambda\sigma. $$ In the regime where the $2 \times 2$ pivot is forced, the controlling scale satisfies $σ \leq λ / α$ is not assumed; instead one uses that the block is chosen on the column-pair realising $λ$ , and the conservative bound $λσ \leq λ^{2} / (1)$ valid because the strategy enters this branch precisely when no single entry of magnitude exceeding $λ$ qualifies a $1 \times 1$ pivot. Substituting $α^{2} λσ \leq α^{2} λ^{2}$ in that regime yields $∣ det E ∣ > λ^{2} - α^{2} λ^{2} = (1 - α^{2}) λ^{2}$ , which is strictly positive since $0 < α < 1$ . Hence $E$ is nonsingular and the recursion proceeds. $□$

Proposition 4 (inertia identity). For symmetric nonsingular $A$ with $P A P^{⊤} = L D L^{⊤}$ produced by the diagonal pivoting method, $inertia (A) = inertia (D)$ , and $inertia (D) = \sum_{blocks} inertia (block)$ with each $2 \times 2$ block contributing $(1, 1, 0)$ .

Proof. By Sylvester's law of inertia, congruent symmetric matrices have equal inertia. The permutation $P$ is orthogonal, so $A$ and $P A P^{⊤}$ are congruent (via $X = P$ ) and share inertia. The factorization gives $P A P^{⊤} = L D L^{⊤}$ , exhibiting $P A P^{⊤}$ as congruent to $D$ via the nonsingular unit-lower-triangular $L$ , so $inertia (P A P^{⊤}) = inertia (D)$ ; chaining gives $inertia (A) = inertia (D)$ . For the blockwise count, $D = diag (D_{1}, \dots, D_{q})$ and the spectrum of a block-diagonal matrix is the union of the block spectra, so the inertia adds blockwise. A $1 \times 1$ block contributes $(1, 0, 0)$ or $(0, 1, 0)$ by the sign of the pivot. A $2 \times 2$ block produced by the strategy has $det < 0$ : it is selected exactly when no admissible $1 \times 1$ pivot exists, forcing $∣ a_{11} a_{r r} ∣ < a_{r 1}^{2}$ in the relevant scaling, so $det E = a_{11} a_{r r} - a_{r 1}^{2} < 0$ , and a symmetric $2 \times 2$ matrix of negative determinant has one positive and one negative eigenvalue, contributing $(1, 1, 0)$ . Summing over blocks gives $inertia (D)$ from the pivot data alone, and $n_{0} = 0$ because $A$ is nonsingular. $□$

Connections Master

Cholesky factorization and the symmetric positive-definite solve 43.03.02 is the definite special case of this unit: when $A$ is positive-definite, the Bunch-Kaufman strategy accepts every pivot as a positive $1 \times 1$ block, no $2 \times 2$ block ever arises, and the block $L D L^{⊤}$ collapses to the root-free Cholesky $L D L^{⊤}$ of that unit. This unit owns the indefinite generalisation that keeps the symmetry-halved cost when definiteness fails; that unit owns the $ρ_{n} \leq 1$ unconditional stability that the indefinite case must relax to a controlled but nonconstant growth factor. The shared object is the symmetric Schur-complement recursion, which both factorizations are instances of.
Gaussian elimination, LU factorization, and its stability 43.03.01 supplies the growth-factor and backward-error framework this unit specialises: the diagonal pivoting method is the symmetric analogue of $P A = LU$ , the threshold $α = (1 + 17) /8$ is the symmetric counterpart of the partial-pivoting bound $∣ ℓ_{ik} ∣ \leq 1$ , and Bunch-Parlett complete pivoting mirrors complete pivoting for $LU$ . The element-growth analysis and the floating-point backward-error charging are imported verbatim from that unit; what changes is that pivoting must act symmetrically as $P A P^{⊤}$ to preserve the diagonal and allow one triangle to do the work of two.
Quadratic forms and positive-definiteness 01.01.15 furnishes Sylvester's law of inertia, the invariance of the signature $(n_{+}, n_{-}, n_{0})$ under congruence, which is what lets the pivot signs of $D$ read off the inertia of $A$ . The indefiniteness that defines this unit's setting is exactly the quadratic-form positivity of that unit failing, and the $2 \times 2$ pivots are forced precisely by the directions in which $x^{⊤} A x$ goes negative. This unit turns the abstract inertia of that unit into a $\frac{1}{3} n^{3}$ computation and into the spectrum-slicing tool for counting eigenvalues in an interval.
The spectral theorem 01.01.13 guarantees that a real symmetric matrix has real eigenvalues and an orthonormal eigenbasis, so the inertia $(n_{+}, n_{-}, n_{0})$ is well defined and the $2 \times 2$ pivot blocks — themselves symmetric — have real eigenvalues of opposite sign. Where the spectral decomposition diagonalises $A$ orthogonally at $O (n^{3})$ eigenvalue cost, the block $L D L^{⊤}$ of this unit congruence-diagonalises it into $1 \times 1$ and $2 \times 2$ blocks at the same asymptotic cost but without solving any eigenvalue problem, trading exact eigenvalues for the cheaper inertia and the linear solve.
Perturbation and a-posteriori error for linear systems 43.03.03 consumes the backward-error bound proved here: once $P (A + E) P^{⊤} = \tilde{L} \tilde{D} \tilde{L}^{⊤}$ with $∥ E ∥ = O (g_{n} ϵ_{mach} ∥ A ∥)$ , the forward-error and residual machinery of that unit converts it into a solution-accuracy guarantee $κ (A) g_{n} ϵ_{mach}$ for the symmetric indefinite solve. The bounded- $L$ defect of Bunch-Kaufman matters exactly there: the system solve stays accurate, but factorization-derived quantities inherit the $L$ growth that rook pivoting removes.

Historical & philosophical context Master

The systematic treatment of symmetric indefinite systems as a distinct numerical problem dates to the early 1970s, when James R. Bunch and Beresford N. Parlett introduced the diagonal pivoting method with $1 \times 1$ and $2 \times 2$ pivots in Direct Methods for Solving Symmetric Indefinite Systems of Linear Equations (SIAM Journal on Numerical Analysis 8, 1971, 639-655), establishing the complete-pivoting strategy and its growth bound. The reduction of the pivot search from the $O (n^{3})$ whole-submatrix scan to an $O (n^{2})$ one-column search, with the threshold constant $α = (1 + 17) /8$ and the use of the pivot signs to compute inertia, came from James R. Bunch and Linda Kaufman in Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems (Mathematics of Computation 31, 1977, 163-179) ^{[Bunch, J. R. & Kaufman, L. — Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems]}, the algorithm that became the LAPACK routine for symmetric indefinite factorization.

The later analytical history is the recognition of the bounded- $L$ defect. Nicholas Higham, in Accuracy and Stability of Numerical Algorithms (SIAM, 1996; 2nd ed. 2002) ^{[Higham, N. J. — Accuracy and Stability of Numerical Algorithms (2nd ed.)]}, gave the componentwise backward-error analysis showing that Bunch-Kaufman is backward stable for the linear solve despite an unbounded $L$ , and the rook-pivoting (bounded Bunch-Kaufman) variant that bounds both growth and $L$ was developed by Cleve Ashcraft, Roger Grimes, and John Lewis in Accurate Symmetric Indefinite Linear Equation Solvers (SIAM Journal on Matrix Analysis and Applications 20, 1998, 513-561). The factorization's role in saddle-point and KKT solvers connects it to the optimisation literature of Magnus Hestenes and the equilibrium systems of mixed finite elements, where the inertia count certifies second-order optimality.

Bibliography Master

@book{golubvanloan2013,
  author    = {Golub, Gene H. and Van Loan, Charles F.},
  title     = {Matrix Computations},
  edition   = {4},
  publisher = {Johns Hopkins University Press},
  year      = {2013}
}

@book{higham2002accuracy,
  author    = {Higham, Nicholas J.},
  title     = {Accuracy and Stability of Numerical Algorithms},
  edition   = {2},
  publisher = {Society for Industrial and Applied Mathematics},
  year      = {2002}
}

@article{bunchparlett1971,
  author  = {Bunch, James R. and Parlett, Beresford N.},
  title   = {Direct Methods for Solving Symmetric Indefinite Systems of Linear Equations},
  journal = {SIAM Journal on Numerical Analysis},
  volume  = {8},
  number  = {4},
  year    = {1971},
  pages   = {639--655}
}

@article{bunchkaufman1977,
  author  = {Bunch, James R. and Kaufman, Linda},
  title   = {Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems},
  journal = {Mathematics of Computation},
  volume  = {31},
  number  = {137},
  year    = {1977},
  pages   = {163--179}
}

@article{ashcraftgrimeslewis1998,
  author  = {Ashcraft, Cleve and Grimes, Roger G. and Lewis, John G.},
  title   = {Accurate Symmetric Indefinite Linear Equation Solvers},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  volume  = {20},
  number  = {2},
  year    = {1998},
  pages   = {513--561}
}

Prerequisites

43.03.02
43.03.01

Tier anchors

beginner: Golub-Van Loan 2013 *Matrix Computations* 4e (Johns Hopkins) §4.4 (symmetric indefinite systems, why Cholesky fails and what a block factorization buys); Trefethen-Bau 1997 *Numerical Linear Algebra* (SIAM) Lecture 23 (the symmetric story Cholesky tells for the definite case, set against the indefinite one)
intermediate: Golub-Van Loan 2013 *Matrix Computations* 4e (Johns Hopkins) §4.4 (the block LDL^T factorization PAP^T = LDL^T with 1x1 and 2x2 pivots, the Bunch-Kaufman diagonal-pivoting search and its O(n^2) cost, the bounded element growth); Higham 2002 *Accuracy and Stability of Numerical Algorithms* 2e (SIAM) Ch. 11 (the backward-error analysis of the diagonal pivoting method)
master: Higham 2002 *Accuracy and Stability of Numerical Algorithms* 2e (SIAM) Ch. 11 (the componentwise backward-error analysis of symmetric-indefinite factorization, the growth-factor bounds for Bunch-Parlett complete pivoting and Bunch-Kaufman partial pivoting, the bounded-L caveat and rook pivoting); Golub-Van Loan 2013 *Matrix Computations* 4e (Johns Hopkins) §4.4; Bunch-Kaufman 1977 *Mathematics of Computation* 31 (the partial-pivoting strategy and the inertia computation)

References

Golub, G. H. & Van Loan, C. F. — Matrix Computations (4th ed.) · Johns Hopkins University Press, 2013. §4.4: the symmetric indefinite factorization P A P^T = L D L^T with D block-diagonal of 1x1 and 2x2 pivots, the Bunch-Parlett complete-pivoting and Bunch-Kaufman partial-pivoting strategies, the bound on element growth and on the entries of L, the n^3/3 flop count and half-storage advantage over unsymmetric LU, and the computation of inertia from the signs of the pivots.
Higham, N. J. — Accuracy and Stability of Numerical Algorithms (2nd ed.) · SIAM, 2002. Ch. 11: the backward-error analysis of the diagonal pivoting method for symmetric indefinite matrices, the growth-factor bound for Bunch-Kaufman partial pivoting and the contrasting bounded-L behaviour of Bunch-Parlett complete pivoting and of rook (bounded Bunch-Kaufman) pivoting, and the stability of the resulting linear solve.
Bunch, J. R. & Kaufman, L. — Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems · Mathematics of Computation 31 (1977), 163-179. The partial-pivoting diagonal strategy with the constant alpha = (1 + sqrt(17))/8 that selects a 1x1 or 2x2 pivot from one column search, the O(n^2) total pivot-search cost, the element-growth bound, and the use of the pivot signs to read off the inertia by Sylvester's law.

Estimated time

beginner: 20m
intermediate: 45m
master: 90m