# Trying to prove nonsingularity of a matrix.

Suppose the matrix $$A\in\mathbb{R}^{m \times n}$$ has full rank, $$x\neq0\in\mathbb{R}^n, b\in\mathbb{R}^m$$ and $$Ax \neq b$$. Denote $$I \in \mathbb{R}^{n\times n}$$ the identity matrix.

Does it hold for all $$\alpha > 0 \in \mathbb{R}$$ that the following matrix is nonsingular:

$$J = \begin{pmatrix}A^T A + \alpha I & x \\ (Ax-b)^T A & 0 \end{pmatrix} ?$$

The matrix $$A^T A + \alpha I$$ is obviously positive definite and hence invertible. Since $$\det(J) = -(Ax-b)^T A(A^T A + \alpha I )^{-1} x\hspace{0.3cm} \underbrace{\det(A^T A + \alpha I)}_{> 0}$$, it would be sufficient to prove that the Schur complement $$S = -(Ax-b)^T A(A^T A + \alpha I )^{-1} x$$ is nonzero.

This is not true. Consider, e.g. $$m=n=2,\ A=I_2,\ x=\pmatrix{1\\ 1},\ b=\pmatrix{-1\\ 3},\ \alpha=1, \ J=\pmatrix{2&0&1\\ 0&2&1\\ 2&-2&0}.$$ In fact, when $$A$$ and $$\alpha$$ are given and $$(m,n)\ne(1,1)$$, we can always pick some vectors $$x$$ and $$b$$ such that $$Ax-b\ne0$$ but $$-(Ax-b)^TA(A^TA+\alpha I)^{-1}x=0$$:
• When $$m>n$$, pick any $$x\in\mathbb R^n$$, any nonzero vector $$z\in\ker(A^T)$$ and set $$b=Ax-z$$.
• When $$n>m$$, pick any $$x\in\ker\left(A(A^TA+\alpha I)^{-1}\right)$$ and any $$b\ne Ax$$.
• When $$m=n>1$$, pick any nonzero vector $$y\in\mathbb R^n$$ such that $$y^Tx=0$$ and set $$z^T=y^T(A^TA+\alpha I)A^{-1}$$ and $$b=Ax-z$$.