# How to show the matrix is invertible

I have a $$A \in R^{m \times n}$$ of rank $$n$$ and $$I$$ is $$m \times m$$ matrix. How to show that the below matrix is invertible?

$$\begin{pmatrix} I & A \\ A^* & 0 \\ \end{pmatrix}$$

Note that since rank of $$A$$ is $$n$$, we have $$n\leq m$$ and $$A^*A$$ is invertible. Therefore, if we write the LDU decomposition of the block matrix into an upper triangular, diagonal, and lower triangular matrices (see e.g. the proof of matrix inversion lemma here), we obtain the inverse to be $$\begin{bmatrix} I & A\\ A^*& 0 \end{bmatrix}^{-1} =\begin{bmatrix} I & A\\ 0 & I \end{bmatrix} \begin{bmatrix} I& 0\\ 0 & (A^*A)^{-1} \end{bmatrix} \begin{bmatrix} I & 0\\ -A^* & I \end{bmatrix}.$$

There exists $$B\in\Bbb R^{n\times m}$$ such that $$BA$$ is the $$n\times n$$ identity. Play with it.

HINT

Recall that a matrix is invertible if and only if it is full rank.

What is the rank of $$\begin{bmatrix} I & A \\ A^* & 0 \\ \end{bmatrix} \in\Bbb R^{(m+n)\times (m+n)}$$?

You can do block Gaussian elimination; for simplicity, set $$C=A^*A$$ which is invertible, because it has full rank: if a vector satisfies $$Cx=0$$, then $$x^*Cx=0$$, which implies $$Ax=0$$ and therefore $$x=0$$ by the assumption on $$A$$.

\begin{align} \left[\begin{array}{cc|cc} I & A & I & 0\\ A^* & 0 & 0 & I \end{array}\right] &\to \left[\begin{array}{cc|cc} I & A & I & 0\\ 0 & -A^*A & -A^* & I \end{array}\right] && R_2\gets R_2-A^*R_1 \\[6px]&\to \left[\begin{array}{cc|cc} I & A & I & 0\\ 0 & I & C^{-1}A^* & -C^{-1} \end{array}\right] && R_2\gets -C^{-1}R_2 \\[6px]&\to \left[\begin{array}{cc|cc} I & 0 & I-AC^{-1}A^* & AC^{-1}\\ 0 & I & C^{-1}A^* & -C^{-1} \end{array}\right] && R_1\gets R_1-AR_2 \end{align} Thus $$\begin{bmatrix} I & A \\ A^* & 0 \end{bmatrix}^{-1}= \begin{bmatrix} I-AC^{-1}A^* & AC^{-1}\\ C^{-1}A^* & -C^{-1} \end{bmatrix}$$