ECSE 506: Stochastic Control and Decision Theory

Aditya Mahajan
Winter 2022

About  |  Lectures  |  Notes  |  Coursework

Positive definite matrices
[WARNING] Citeproc: citation Abbasi-Yadkori2011 not found

1 Definite and basic properties

Definition

A \(n \times n\) symmetric matrix \(M\) is called

  • positive definite (written as \(M > 0\)) if for all \(x \in \reals^n\), \(x \neq 0\), we have \[x^\TRANS M x > 0.\]

  • positive semi definite (written as \(M \ge 0\)) if for all \(x \in \reals^n\), \(x \neq 0\), we have \[x^\TRANS M x \ge 0.\]

1.1 Examples

1.2 Remarks on positive definite matrices

  1. By making particular choices of \(x\) in the definition of positive definite matrix, we have that for a positive definite matrix \(M\),

    • \(M_{ii} > 0\) for all \(i\)
    • \(M_{ij} < \sqrt{M_{ii} M_{jj}}\) for all \(i \neq j\).

    However, satisfying these inequalities is not sufficient for positive definiteness.

  2. A symmetric matrix is positive definite (respt. postive semi-definite) if and only if all of its eigenvalues are positive (respt. non-negative).

  3. Therefore, a sufficient condition for a symmetric matrix to be positive definite is that all diagonal elements are positive and the matrix is diagonally dominant, i.e., \(M_{ii} > \sum_{j \neq i} | M_{ij}|\) for all \(i\).

  4. If \(M\) is symmetric positive definite, then so is \(M^{-1}\).

  5. If \(M\) is symmetric positive definite, then \(M\) has a unique symmetric positive definite square root \(R\) (i.e., \(RR = M\)).

  6. If \(M\) is symmetric positive definite, then \(M\) has a unique Cholesky factorization \(M = T^\TRANS T\), where \(T\) is upper triangular with positive diagonal elements.

  7. The set of positive semi-definite matrices forms a convex cone.

  8. Positive definiteness introduces a partial order on the convex cone of positive semi-definite matrices. In particular, we say that for two positive semi-definite matrices \(M\) and \(N\) of the same dimension, \(M \succeq N\) if \(M - N\) is positive semi-definite. For this reason, often \(M \succ 0\) and \(M \succeq 0\) is used a short-hand to denote that \(M\) is positive definite and positive semi-definite.

  9. Let \(M\) is a symmetric square matrix. Let \[ λ_1(M) \ge λ_2(M) \ge \dots \ge λ_n(M) \] denote the ordered (real) eigenvalues of \(M\). Then \[ λ_1(M)I \succeq M \succeq λ_n(M)I. \]

  10. If \(M \succeq N\), then \[ λ_k(M) \ge λ_k(N), \quad k \in \{1, \dots, n\}. \]

  11. If \(M \succeq N \succ 0\), then \[ N^{-1} \succeq M^{-1} \succ 0. \]

  12. If \(M \succeq N\) are \(n × n\) matrices and \(T\) is a \(m × n\) matrix, then \[ T^\TRANS M T \succeq T^\TRANS N T. \]

  13. If \(M, N\) are \(n×\) positive semi-definite matrices, then \[ \sum_{i=1}^k λ_i(M) λ_{n-i+1}(N) \le \sum_{i=1}^k λ_i(MN) \le \sum_{i=1}^k λ_i(M)λ_i(N), \quad k \in \{1, \dots, n\}. \] Note that this property does not require \(M - N\) to be positive or negative semi-definite.

  14. If \(M \succ 0\) and \(T\) are square matrices of the same size, then \[ TMT + M^{-1} \succeq 2T. \]

1.3 A useful relationships.

Symmetric block matrices of the form

\[ C = \MATRIX{ A & X \\ X^\TRANS B } \]

often appear in applications. If \(A\) is non-singular, we can write

\[ \MATRIX{A & X \\ X^\TRANS B } = \MATRIX{I & 0 \\ X^\TRANS A^{-1} & I} \MATRIX{A & 0 \\ 0 & B - X^\TRANS A^{-1} X } \MATRIX{I & A^{-1} X \\ 0 & I } \] which shows that \(C\) is congruent to a block diagonal matrix, which is positive definite when its diagonal blocks are postive definite. Therefore, \(C\) is positive definite if and only if both \(A\) and \(B - X^\TRANS A^{-1} X\) are positive definite. The matrix \(B = X^\TRANS A^{-1} X\) is called the Shur complement of \(A\) in \(C\).

1.4 Determinant bounds

Fischer’s inequality. Suppose \(A\) and \(C\) are positive semidefinite matrix and \[ M = \MATRIX{A & B \\ B^\TRANS & C}. \] Then \[ \det(M) \le \det(A) \det(C). \]

Recursive application of Fischer’s inequality gives the Hadamard’s inequality for a symmetric positive definite matrix: \[ \det(A) \le A_{11} A_{22} \cdots A_{nn}, \] with equality if and only if \(A\) is diagonal.

Prop. 1

If \(M \succ N \succ 0\) are \(n × n\) matrices and \(T\) is a \(m × n\) matrix, then \[ \sup_{ T \neq 0} \frac{ \| T^\TRANS M T \| }{ \| T^\TRANS N T \|} \le \frac{ \det(M) }{ \det(N) }, \] where for any matrix \(M\), \[ \| M \| = \sup_{x \neq 0} \frac{ \| M x \|_2 }{ \|x\|_2 } \] is the \(2\)-norm of the matrix.

Prop. 1 is taken from (Abbasi-Yadkori2011?).

References

The properties of positive definite matrices are stated in any book on the theory of matrices. See for example Marshall et al. (2011).

Historically, a matrix used as a test matrix for testing positive definiteness was the Wilson matrix \[ W = \MATRIX{5 & 7 & 6 & 5 \\ 7 & 10 & 8 & 7 \\ 6 & 8 & 10 & 9 \\ 5 & 7 & 9 & 10}. \] For a nice overview of Wilson matrix, see this blog post.


Marshall, A.W., Olkin, I., and Arnold, B.C. 2011. Inequalities: Theory of majorization and its applications. Springer New York. DOI: 10.1007/978-0-387-68276-1.

This entry was last updated on 14 Aug 2020