Back to Math Tools
Back to notes

# Positive Definite and Positive Semidefinite Matrices

Positive definite (PD) and positive semidefinite (PSD) matrices are very useful and appear everywhere in TCS. Recall that we say a matrix $A\in\bbR^{n\times n}$ is PD (resp. PSD) if $A$ is symmetric and all its eigenvalue is positive (resp. non-negative). Let us start with some simple equivalent definitions of PSness and PSDness.

Let $A\in\bbR^{n\times n}$ be symmetric. The following are equivalent.
• $A$ is PS.
• All of $A$'s eigenvalues are positive.
• For any $\bx\in\bbR^n$, $\bx^\top A\bx>0$.
• Write $A$ as a block matrix \begin{bmatrix} A_{11}&A_{12}\\A_{21}&A_{22} \end{bmatrix} and both $A_{11}$ as well as the Schur complement $S=A_{22}-A_{21}A_{11}^{}$ are PS.
• Let $A\in\bbR^{n\times n}$ be symmetric. The following are equivalent.
• $A$ is PSD.
• All of $A$'s eigenvalues are non-negative.
• For any $\bx\in\bbR^n$, $\bx^\top A\bx\geq0$.
• There exists $B\in\bbR^{n\times n}$ such that $A=B^\top B$.
• ## Some useful properties of PSD matrices

### Hadamard product of PSD matrices

Define the Hadamard product of two matrices $A,B$ as the entrywise product and denote it as $A\circ B$.

The Schur product theorem states that the Hadamaard product of two PSD matrices is still PSD.

Let $A,B\in\bbR^{n\times n}$ be PSD. Then, $A\circ B$ is also PSD.

When $B$ is rank-1, i.e., $B=\bx^\top\bx$ , then $A\circ B$ is clearly PSD since $\tr(A\circ B)=\bx^\top A\bx\geq0$ and $\rank(A\circ B)\leq1$. Next, consider the case where $\rank(B)=k>1$. In this case, we write $B=\sum_{i\in[k]}\lambda_i\bx_i\bx_i^\top$ where $\lambda_i\geq0$. Then, $A\circ B=\sum_{i\in[k]}\lambda_i\cdot A\circ (\bx_i\bx_i^\top)$. As $A\circ (\bx_i\bx_i^\top)$ is PSD and the non-negative weighted sum of PSD matrices is still PSD, we conclude that $A\circ B$ is PSD.

Another immediate corollary of Schur product theorem is the following.

Let $A\in\bbR^{n\times n}$ be PSD. Then $A^{\circ k}$ is also PSD for all $k\in\N$ where $A^{\circ k}_{ij} = (A_{ij})^k$.

The following Fejer’s theorem gives another characterization of PSD matrix .

Let $A\in\bbR^{n\times n}$. $A$ is PSD if and only if for all PSD matrix $B\in\bbR^{n\times n}$, \begin{equation*} \sum_{i,j\in[n]}A_{ij}B_{ij}\geq0. \end{equation*}

It is easy to see that if $A$ is PSD, then the equation holds for all PSD matrix $B$ from Schur product theorem. As for the converse, consider arbitrary $\bx\in\bbR^n$ and let $B=\bx\bx^\top$. Clearly that $B$ is PSD and thus $\sum_{i,j\in[n]}A_{ij}B_{ij}\geq0$. Note that the summation is actually \begin{equation*} \sum_{i,j\in[n]}A_{ij}B_{ij} = \bx^\top A\bx. \end{equation*} Since $\bx$ is arbitrary, we conclude that $A$ is PSD.

Another useful fact about the Hadamard product of two PSD matrices is the following.

Let $A,B\in\bbR^{n\times n}$ be PSD. Then, \begin{equation*} \det(A\circ B)\geq\det(A)\cdot\det(B). \end{equation*}