# Sufficient and necessary condition for $N^{\top}MN$ to be invertible

Let M be a symmetric positive semi-definite matrix. Let N be a matrix with linearly independent columns, but not necessarily a square matrix. What is the necessary and sufficient condition for $N^{\top}MN$ to be invertible? It seems that $N^{\top}MN$ is invertible iff. $M$ is positive definite or $M$ is invertible. How would you go about proving/disproving the condition?

We can show that if $x$ is a solution to $N^{\top}MNx=0$, then $\left(Nx\right)^{\top}M\left(Nx\right)=0$. If $M$ is positive definite, $x$ can only be 0, which proves that $M$ being positive definite is a sufficient condition.

Now the question becomes whether $M$ being positive definite is a necessary condition?

Suppose $$M = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$$ and $$N = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$ Then $N^t M N = $ is invertible, but $M$ is not positive definite. Perhaps you should consider this case, unless $N$ is known to be square and you just forgot to mention it.
If $N$ is square, then "$M$ invertible" is the right condition, yes. For if $N$ is square and has independent columns, then its inverse exists. So $N^t M N$ is invertible iff $M$ is invertible. [Sorry about my earlier answer where I said "positive def" was the right condition -- I was thinking about a related but different problem about the existence of square roots of matrices...]
If $M$ is positive semidefinite and $N$ has full column rank, then $N^TMN$ is positive definite if and only if $M$ is positive definite on the image of $N$, that is, $x^TMx>0$ for all $x\in\mathrm{Im}(N)\setminus\{0\}$.