ECSE 506: Stochastic Control and Decision Theory
Aditya Mahajan
Winter 2022
About  Lectures  Notes  Coursework
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
\(\MATRIX{ x_1 & x_2 } \MATRIX{ 3 & 0 \\ 0 & 2 } \MATRIX{ x_1 \\ x_2 } = 3 x_1^2 + 2 x_2^2\).
Thus, \(\MATRIX{ 3 & 0 \\ 0 & 2 } > 0\).
\(\MATRIX{ x_1 & x_2 } \MATRIX{ 0 & 0 \\ 0 & 2 } \MATRIX{ x_1 \\ x_2 } = 2 x_2^2\).
Thus, \(\MATRIX{ 0 & 0 \\ 0 & 2 } \ge 0\).
1.2 Remarks on positive definite matrices
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.
A symmetric matrix is positive definite (respt. postive semidefinite) if and only if all of its eigenvalues are positive (respt. nonnegative).
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\).
If \(M\) is symmetric positive definite, then so is \(M^{1}\).
If \(M\) is symmetric positive definite, then \(M\) has a unique symmetric positive definite square root \(R\) (i.e., \(RR = M\)).
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.
The set of positive semidefinite matrices forms a convex cone.
Positive definiteness introduces a partial order on the convex cone of positive semidefinite matrices. In particular, we say that for two positive semidefinite matrices \(M\) and \(N\) of the same dimension, \(M \succeq N\) if \(M  N\) is positive semidefinite. For this reason, often \(M \succ 0\) and \(M \succeq 0\) is used a shorthand to denote that \(M\) is positive definite and positive semidefinite.
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. \]
If \(M \succeq N\), then \[ λ_k(M) \ge λ_k(N), \quad k \in \{1, \dots, n\}. \]
If \(M \succeq N \succ 0\), then \[ N^{1} \succeq M^{1} \succ 0. \]
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. \]
If \(M, N\) are \(n×\) positive semidefinite matrices, then \[ \sum_{i=1}^k λ_i(M) λ_{ni+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 semidefinite.
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 nonsingular, 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 (AbbasiYadkori2011?).
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.
This entry was last updated on 14 Aug 2020