How to show this matrix is positive semidefinite?

Question

Let

$$K=\begin{pmatrix} K_{11} & K_{12}\\ K_{21} & K_{22} \end{pmatrix}$$

be a symmetric positive semidefinite real matrix (PSD) with $K_{12}=K_{21}^T$. Then, for $|r| \le 1$,

$$K^*=\begin{pmatrix} K_{11} & rK_{12}\\ rK_{21} & K_{22} \end{pmatrix}$$

is also a PSD matrix. Matrices $K$ and $K^*$ are $2 \times 2$ and $K_{21}^T$ denotes the transpose matrix. How do I prove this?

Answer 1

This is a nice opportunity to apply the definitions: no advanced theorems are needed.

To simplify the notation, for any number $\rho$ let $$\mathbb{A}(\rho)=\pmatrix{A&\rho B\\\rho B^\prime&D}$$ be a symmetric block matrix. (If working with block matrices is unfamiliar to you, just assume at first that $A$, $B$, $D$, $x$, and $y$ are numbers. You will get the general idea from this case.)

For $\mathbb{A}(\rho)$ to be positive semidefinite (PSD) merely means that for all vectors $x$ and $y$ of suitable dimensions

$$\eqalign{ 0 &\le \pmatrix{x^\prime&y^\prime} \mathbb{A}(\rho) \pmatrix{x\\y} \\ &= \pmatrix{x^\prime&y^\prime} \pmatrix{A&\rho B\\\rho B^\prime&D}\pmatrix{x\\y} \\ &=x^\prime A x + 2\rho y^\prime B^\prime x + y^\prime D y.\tag{1} }$$

This is what we have to prove when $|\rho|\le 1$.

We are told that $\mathbb{A}(1)$ is PSD. I claim that $\mathbb{A}(-1)$ also is PSD. This follows by negating $y$ in expression $(1)$: as $\pmatrix{x\\y}$ ranges through all possible vectors, $\pmatrix{x\\-y}$ also ranges through all possible vectors, producing

$$\eqalign{ 0 &\le \pmatrix{x^\prime&-y^\prime}\mathbb{A}(1)\pmatrix{x\\-y} \\ &= x^\prime A x + 2(-y)^\prime B^\prime x + (-y)^\prime D (-y) \\ &= x^\prime A x + 2(-1)y^\prime B^\prime x + y^\prime D y \\ &= \pmatrix{x^\prime&y^\prime}\mathbb{A}(-1)\pmatrix{x\\y}, }$$

showing that $(1)$ holds with $\rho=-1.$

Notice that $\mathbb{A}(\rho)$ can be expressed as a linear interpolant of the extremes $\mathbb{A}(-1)$ and $\mathbb{A}(1)$:

$$\mathbb{A}(\rho) = \frac{1-\rho}{2}\mathbb{A}(-1) + \frac{1+\rho}{2}\mathbb{A}(1).\tag{2}$$

When $|\rho|\le 1$, both coefficients $\color{blue}{(1-\rho)/2}$ and $\color{blue}{(1+\rho)/2}$ are non-negative. Therefore, since both ${\pmatrix{x^\prime&y^\prime}\mathbb{A}(1)\pmatrix{x\\y}}$ and $\pmatrix{x^\prime&y^\prime}\mathbb{A}(-1)\pmatrix{x\\y}$ are nonnegative, so is the right hand side of

$$\eqalign{ &\pmatrix{x^\prime&y^\prime}\mathbb{A}(\rho)\pmatrix{x\\y} \\ &= \color{blue}{\left(\frac{1-\rho}{2}\right)}\pmatrix{x^\prime&y^\prime}\mathbb{A}(-1)\pmatrix{x\\y} + \color{blue}{\left(\frac{1+\rho}{2}\right)}\pmatrix{x^\prime&y^\prime}\mathbb{A}(1)\pmatrix{x\\y} \\ &\ge \color{blue}{0}(0) + \color{blue}{0}(0) = 0. }$$

(I use colors to help you see the four separate non-negative terms that are involved.)

Because $x$ and $y$ are arbitrary, we have proven $(1)$ for all $\rho$ with $|\rho|\le 1$.

Answer 2

There is already a great answer by @whuber, so I will try to give an alternative, shorter proof, using a couple theorems.

1. For any $A$ - PSD and any $Q$ we have $Q^TAQ$ - PSD
2. For $A$ - PSD and $B$ - PSD also $A + B$ - PSD
3. For $A$ - PSD and $q > 0$ also $qA$ - PSD

And now:

\begin{align*} K^* &= \begin{pmatrix} K_{1,1} & rK_{1,2} \\ rK_{2,1} & K_{2,2} \\ \end{pmatrix} \\ &= \begin{pmatrix} K_{1,1} & rK_{1,2} \\ rK_{2,1} & r^2K_{2,2} \\ \end{pmatrix} + \begin{pmatrix} 0 & 0 \\ 0 & qK_{2,2} \\ \end{pmatrix}, \text{ where $q = 1 - r^2 > 0$} \\ &= \begin{pmatrix} I & 0 \\ 0 & rI \\ \end{pmatrix}^T \begin{pmatrix} K_{1,1} & K_{1,2} \\ K_{2,1} & K_{2,2} \\ \end{pmatrix} \begin{pmatrix} I & 0 \\ 0 & rI \\ \end{pmatrix} + q\begin{pmatrix} 0 & 0 \\ 0 & K_{2,2} \\ \end{pmatrix} \end{align*}

Matrix $K$ is PSD by definition and so is its submatrix $K_{2, 2}$