I have the following matrix $M \in \mathbb{R}^{(n+1) x (n+1)}$:
$M= \left[ \begin{array}{c|c} AA^t & 2b \\ \hline 0^t & 1 \end{array} \right]$
where $A \in \mathbb{R}^{n x n}$ and $b \in \mathbb{R}^n \neq \vec 0$.
I want to prove that if A is non-singular and $||A^-1 b||_2^2 < 1$ $\Rightarrow M$ is positive definite.
I started by taking a non-zero $\vec v = (x, \alpha)$, with $x \in \mathbb{R}^n$ and $\alpha \in \mathbb{R}$, and doing block product $x^t M x$. That yields the following equation:
$x^t M x = \alpha^2 + \alpha (2 x^t b) + x^t A A ^t x$.
For $M$ to be positive definite: $x^t M x > 0$, so if that quadratic equation is always positive the implication would hold.
I take its discriminant:
$b^2 - 4ac = 4 [(x^t b)^2 + x^t A A ^t x] = x^t (b - AA^tx)$.
And at that point I'm stuck. Is there a way of rewriting $||A^-1 b||_2^2$ in order to use it in that equation that I'm missing? Or is this a dead end?
You computed the discriminant incorrectly. $$4(x^t b b^t x - x^t A A^t x)=4x^t (bb^t - AA^t)x = 4 x^t A((A^{-1} b)(A^{-1} b)^t - I) A^t x.$$
The matrix $(A^{-1} b)(A^{-1} b)^t - I$ is symmetric, so if we show all eigenvalues are negative, then this matrix is negative definite, so the above discriminant is negative, which would conclude the proof.
The eigenvalues of $(A^{-1} b)(A^{-1} b)^t - I$ can be obtained by taking eigenvalues of $(A^{-1} b)(A^{-1} b)^t$ and subtracting $1$. Show that one eigenvalue of this latter matrix is $\|A^{-1} b\|_2$, and that the rest are zero.
More direct approach:
If $y$ and $v$ are vectors with $\|v\| < 1$, then Cauchy-Schwarz implies $$y^t(vv^t - I)y = (v^t y)^2 - \|y\|^2 \le (\|v\|^2 - 1)\|y\|^2 < 0.$$ Do you see how to apply this to the original problem?