Please help me prove a positive definite matrix!

Question

Prove that:
If $W$ is a diagonal matrix having positive diagonal elements and size $(2^n–1)\text{x}(2^n – 1)$, $K$ is a matrix with size $(2^n – 1)\text{x}n$, then:
$A = K^T[W^{-1} - K(K^TWK)^{-1}K^T]K$
is a positive definite matrix.
Using the Monte-Carlo method, I find that the matrix
$B=W^{-1} - K(K^TWK)^{-1}K^T$
can be negative definite.
Thank you so much for reading my question
I am looking forward to getting your response!

Answer 1

I assume you assume that $K^TWK$ is invertible; I do too.

Let $W^{1/2}$ be a symmetric square root of $W$, and let $L=W^{1/2}K$. Then $$W^{1/2}BW^{1/2} =I-L(K^TWK)^{-1}L^T = I-L(L^TL)^{-1}L^T.$$
This is the matrix of the orthogonal projection onto the null space of $L$, and hence positive semi definite.

In more detail: write the singular value decomposition $L=P\Delta Q$ where $\Delta$ is diagonal, and $Q$ is $n\times n$, we see that $$L(L^TL)^{-1}L'=(U\Delta V)(V^T\Delta^2V)^{-1}(V^T\Delta U^T) = UU^T.$$ Note that $\|U^Tx\|^2\le\|x\|^2$ so $x^T(I-UU^T)x=\|x\|^2-\|U^Tx\|^2\ge0$, verifying the psd claim.

Since $Q^{1/2}$ is invertible, $B$ is also semi positive definite.

I assume the contradiction between this and what the OP asked for is due to a mismatch between the posted question and the Matlab code it describes.