M6-T4 — Positive Definite Matrices

Learning objectives

After this lesson, you should be able to:

• Define positive definite and positive semi-definite symmetric matrices.
• Test positive definiteness with eigenvalues, leading minors and Cholesky.
• Explain why covariance and information matrices must be positive (semi-)definite and what goes wrong otherwise.
• Repair a nearly-indefinite matrix by clipping eigenvalues or adding a diagonal term.

Introduction and motivation

In an Extended Kalman Filter the covariance P is updated thousands of times; rounding errors can push a tiny eigenvalue negative, after which the filter reports a negative variance and the Mahalanobis distance becomes meaningless or the Cholesky factor fails and the robot crashes. Optimisation faces the same issue: a Hessian that is not positive definite does not describe a bowl, so a Newton step can climb uphill. Knowing how to test and repair positive definiteness is basic engineering hygiene.

The intuition

The quadratic form xᵀAx assigns an "energy" to each direction x. If the energy is positive in every direction the surface is a bowl with a single lowest point; this is positive definite. If it is zero along some direction the bowl has a flat trough (positive semi-definite). If some directions go negative, the surface is a saddle (indefinite) and the middle is not a minimum.

Geometric and physical interpretation

Geometric view. Positive definite means the level curves xᵀAx = const are ellipses (ellipsoids): closed bowls, with axes along the eigenvectors and half-lengths 1/√λᵢ at level 1. Semi-definite gives flat valleys (an infinite strip); indefinite gives saddles. Physical view. For a stiffness matrix, positive definite means every displacement stores positive elastic energy. For a covariance it means every direction has non-negative variance; strictly positive means the estimate is not already certain in some direction.

The mathematics

A

a real symmetric n × n matrix.

xᵀAx

the quadratic form, a scalar “energy” for the vector x.

A ≻ 0, A ⪰ 0

positive definite and positive semi-definite.

L

a lower-triangular matrix with positive diagonal entries (the Cholesky factor).

Definition

A ≻ 0  ⇔  xᵀ A x > 0 for all x ≠ 0        A ⪰ 0  ⇔  xᵀ A x ≥ 0 for all x

What it means. Strict positivity of the energy in every non-zero direction. Semi-definite allows zero energy along some directions, which means the matrix is singular.

Equivalent tests

A ≻ 0  ⇔  all eigenvalues λᵢ > 0  ⇔  all leading principal minors > 0  ⇔  A = L Lᵀ with L lower triangular, positive diagonal

What it means. For 2 × 2 [[a, b], [b, c]]: a > 0 and ac − b² > 0. Cholesky is the cheapest test in code: it is attempted anyway when solving or sampling, and it fails exactly for matrices that are not positive definite.

Gram matrices are always semi-definite

xᵀ (BᵀB) x = ‖B x‖² ≥ 0

What it means. Any matrix of the form BᵀB is positive semi-definite, and positive definite exactly when B has full column rank (Bx = 0 only for x = 0). This is why AᵀA in least squares and JᵀJ in Gauss-Newton are valid curvature matrices.

Positive definite = every direction has positive energy = all eigenvalues > 0. Test it with Cholesky; repair it by clipping eigenvalues or adding εI.

Step-by-step derivation: eigenvalue test, 2 × 2 minors and Cholesky

Eigenvalue test. Write A = QΛQᵀ and let y = Qᵀx, so x ≠ 0 ⇔ y ≠ 0 and

1. xᵀAx = yᵀΛy = λ₁y₁² + … + λₙyₙ².
2. If every λᵢ > 0 this sum is positive for any y ≠ 0, so A ≻ 0.
3. Conversely, if some λₖ ≤ 0, choose x = qₖ: xᵀAx = λₖ ≤ 0, contradicting positivity.

2 × 2 minors. For A = [[a, b], [b, c]] the eigenvalues are real with product ac − b² and sum a + c. Both are positive exactly when a > 0 and ac − b² > 0 (the second implies a and c have the same sign; the first picks positive). These are the leading minors.

Cholesky. Seek A = LLᵀ with L = [[l₁₁, 0], [l₂₁, l₂₂]]. Multiplying out: a = l₁₁², b = l₁₁l₂₁, c = l₂₁² + l₂₂². So l₁₁ = √a, l₂₁ = b/l₁₁, l₂₂ = √(c − l₂₁²). The square roots exist exactly when a > 0 and c − b²/a > 0, the same minor conditions. The algorithm generalises row by row and costs about n³/3 operations, half of an LU factorisation.

Repairs. If rounding made one eigenvalue slightly negative: (1) clip: replace λᵢ by max(λᵢ, ε) and rebuild QΛQᵀ (the nearest positive semi-definite matrix in the Frobenius norm when ε = 0); or (2) add a ridge: A + εI shifts every eigenvalue up by ε, the same regularisation used in damped least squares.

A worked example: testing and repairing

• Test. A = [[4, 2], [2, 3]]: a = 4 > 0, ac − b² = 12 − 4 = 8 > 0, so positive definite. Eigenvalues: trace 7, determinant 8, λ = (7 ± √17)/2 = 5.562, 1.438, both positive ✓.
• Cholesky. l₁₁ = 2, l₂₁ = 2/2 = 1, l₂₂ = √(3 − 1) = √2 = 1.414, so L = [[2, 0], [1, √2]], and L Lᵀ = [[4, 2], [2, 1 + 2]] = [[4, 2], [2, 3]] ✓.
• Failure. B = [[1, 1.1], [1.1, 1]] looks like a plausible correlation matrix but ac − b² = 1 − 1.21 = −0.21 < 0; its eigenvalues are 2.1 and −0.1. Cholesky fails at the second pivot (1 − 1.21 < 0): the “correlation” 1.1 exceeds one in magnitude, which is impossible.
• Repair by clipping. Replace −0.1 by a small positive value such as 0.001 and rebuild: the eigenvalues become 2.1 and 0.001, a valid (though nearly singular) covariance.
• Repair by ridge. B + 0.1 I has eigenvalues 2.2 and 0.0, which is only semi-definite; use B + 0.2 I to get 2.3 and 0.1, positive definite.

Robotics application

Kalman filters and SLAM. Every prediction and update must leave P symmetric positive (semi-)definite. The Joseph form of the covariance update is used because it preserves this property under rounding; see the UAV EKF lesson and EKF-SLAM.

Sampling and noise models. To simulate a noisy sensor with covariance Σ, take the Cholesky factor Σ = LLᵀ and use x = μ + L z with z standard normal; this fails if Σ is not positive definite, which is a useful early warning.

Optimisation. Gauss-Newton uses JᵀJ, positive semi-definite by construction; adding λI (Levenberg-Marquardt) makes it strictly positive definite so the step is always a descent direction. See nonlinear least squares.

Control and stability. A Lyapunov function for a robot is often V = xᵀPx with P ≻ 0: it is an energy that must strictly decrease. Controller design is the search for such a P.

Engineering implications and limitations

Practical rules

• Test with Cholesky, not with the determinant. Determinants of large matrices overflow or underflow; Cholesky is cheap and reliable.
• Distinguish definite from semi-definite. A covariance with a zero eigenvalue is legitimate (a deterministic direction) but cannot be inverted or used for a Mahalanobis distance. Information matrices that are only semi-definite signal an unobservable direction (a gauge freedom in SLAM).
• Expect tiny negative eigenvalues from rounding. Treat |λ| below about 1e-12·λmax as zero, not as an error, and then symmetrise and clip.
• Never “fix” a covariance by taking absolute values of entries. Repair through eigenvalues (clip) or add a small multiple of the identity so that structure and symmetry are preserved.
• Make sure a user-supplied correlation matrix is valid. Pairwise-correct correlations can still be jointly impossible (the example above); always test the full matrix.

Limits

Positive definiteness is a statement about symmetric matrices only. A non-symmetric matrix may have positive eigenvalues and still produce negative energy for some x, so symmetrise (or use the symmetric part (A + Aᵀ)/2) before testing the quadratic form.

Common misconceptions

Engineering takeaways

1. Positive definite means xᵀAx > 0 for every non-zero x, equivalently all eigenvalues are positive.
2. Equivalent tests: eigenvalues, leading minors and, in code, whether Cholesky succeeds.
3. BᵀB is always positive semi-definite, positive definite when B has full column rank.
4. Covariances and information matrices must be positive (semi-)definite; rounding can break this, so symmetrise, clip or add εI.
5. Positive semi-definite signals a flat or unobservable direction and a non-invertible matrix.

References and further reading

Primary papers and authoritative documentation.

• MIT 18.06SC Linear Algebra (OCW): lecture on positive definite matrices and minima
• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): Gram matrices and the Cholesky factorisation; the site did not load when we last checked
• Immersive Linear Algebra: chapter 10 sections on definiteness
• UCSD ECE276A: Sensing and Estimation in Robotics: covariance matrices and Cholesky factorisation in estimation

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Symmetric matrices are tidy, but most matrices in robotics (Jacobians, camera matrices, rectangular data matrices) are not symmetric or not even square. The singular value decomposition extends the same rotate, stretch, rotate picture to every matrix.

Related content

Nothing below is required to finish this lesson.

• Before
  M6-T3: Symmetric Matrices

  State the spectral theorem and use the orthogonal eigenbasis of a symmetric matrix.