Show that the difference between a PSD matrix and the block diagonal of its principal sub matrices is also PSD

Let $$A \in \mathbb{R}^{n \times n}$$ denote a positive semi-definite matrix (PSD).

Let $$A_{n_1} \in \mathbb{R}^{n_1 \times n_1}$$ denote the principal submatrix of $$A$$ that corresponds to taking the first $$n_1$$ rows and $$n_1$$ columns. Let $$A_{n_2} \in \mathbb{R}^{n_2 \times n_2}$$ denote the principal submatrix of $$A$$ that corresponds to taking the next $$n_2$$ rows and $$n_2$$ columns, and so forth.

Let $$A_{block} = \text{blkdiag}\{A_{n_j}\}_{j=1}^J$$.

For example, let $$J=$$ and $$n = n_1 + n_2 + n_3$$ where $$n_j \geq 0$$ for all $$j$$. In particular, we can let $$n_1 = n_2 = 2$$, and $$n_3 = 1$$. Then we have:

$$A = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & a_{15} \\ a_{21}& a_{22} & a_{23} & a_{24} & a_{25} \\ a_{31}& a_{32} & a_{33} & a_{34} & a_{35} \\ a_{41}& a_{42} & a_{43} & a_{44} & a_{45} \\ a_{51}& a_{52} & a_{53} & a_{54} & a_{55} \\\end{bmatrix}$$

$$A_{n_1} = \begin{bmatrix} a_{11} & a_{12} \\ a_{21}& a_{22} \\\end{bmatrix}$$

$$A_{n_2} = \begin{bmatrix} a_{33} & a_{34} \\ a_{43}& a_{44} \\\end{bmatrix}$$ $$A_{n_3} = a_{55}$$

$$A_{block} = \begin{bmatrix} a_{11} & a_{12} & 0& 0 & 0 \\ a_{21}& a_{22} & 0 & 0& 0 \\ 0& 0 & a_{33} & a_{34} & 0 \\ 0& 0 & a_{43} & a_{44} & 0\\ 0& 0 & 0 & 0 & a_{55} \\\end{bmatrix}$$

My question: is $$A - A_{\text{block}}$$ positive semi-definite or $$A- \frac{1}{J}A_{\text{block}}$$ PSD?

My attempt: Since $$A_{\text{block}}$$ is the block diagonal matrix of the principal sub matrices of $$A$$, I know that $$\lambda_{min}(A) \leq \lambda_{min}(A_{\text{block}}) \leq \lambda_{max}(A_{\text{block}}) \leq \lambda_{max}(A)$$ where $$\lambda$$ denotes the eigenvalue. However, this is not enough for me to conclude that $$A-A_{\text{block}}$$ is PSD. If $$\lambda_{min}(A) < \lambda_{min}(A_{\text{block}})$$, then $$A-A_{\text{block}}$$ is not PSD.

That's why I turned my attention to $$A- \frac{1}{J}A_{\text{block}}$$. Perhaps it's easier to show that $$A- \frac{1}{J}A_{\text{block}}$$ is PSD. One way is to show that every eigenvalue of $$A- \frac{1}{J}A_{\text{block}}$$ is non-negative. That's why I made a post here asking about the relationship between the eigenvalues of $$A$$ and those of $$A_{\text{block}}$$.

However, I realize that there are other ways of showing whether a matrix is PSD, e.g., showing that all principal minors or the matrix are non-negative. I'm not sure which way would be the most straightforward.

1 Answer

First of all, note that positive (semi)definiteness is defined for symmetric matrices. Pick the positive definite matrix

$$A=\begin{bmatrix}1 & 1\\1 & 2\end{bmatrix}\ \mathrm{for\ which\ we\ have}\ A_{block}=\begin{bmatrix}1 & 0\\0 & 2\end{bmatrix}.$$

In that case, we have $$J=2$$ and

$$A-\dfrac{1}{2}A_{block}=\begin{bmatrix}1/2 & 1\\1 & 1\end{bmatrix}.$$

However, this matrix is not positive semidefinite.

Also, we have that $$A-A_{block}$$ is not positive semidefinite. In fact, this matrix will never be positive semidefinite because of the presence of nonzero off diagonal terms. The only time it will be in whenever $$A=A_{block}$$.

• Thanks, when would $A-\frac{1}{J}A_{block}$ be PSD? Is there a condition under which $A-\frac{1}{J}A_{block}$ is PSD? It seems to me that it could be PSD, but I'm not sure what the condition is. Apr 12, 2022 at 22:47
• Yes, it could be PSD but I do not think there is a general condition on $A$ for that, except perhaps in very special (and uninteresting) cases.
– KBS
Apr 12, 2022 at 22:50