When is $A^TA$ invertible?

Question

Let $A$ be a matrix. What are some necessary/sufficient conditions for the Gram matrix $A^T A$ to be invertible?

This question came up when I was trying to learn about least-squares regression. Is it true that a regression matrix will always have $A^TA$ invertible?

Answer 1

I’m assuming that you’re talking about matrices over a field, e.g. $\mathbb R$ or $\mathbb C$, so that the various definitions of “rank” coincide.

$A^\top A$ is invertible iff it has full rank. It has the same rank as $A$ (since it annihilates the same vectors as $A$ on both sides). So if $A$ is $m\times n$ (so that $A^\top A$ is $n\times n$), then $A^\top A$ is invertible iff $m\ge n$ and $A$ has rank $n$.

I’m not sure what you mean by a “regression matrix”. If you perform linear regression, $A^\top A$ may be singular if you don’t have enough different points to work with or if some of the functions whose linear combination you’re considering are linearly dependent.

Answer 2

If we're talking about an $n \times n$ matrix $A$ over a commutative ring $R$ with identity then $A^TA$ is invertible as a matrix iff $(\det A)^2$ is invertible in $R$ iff $\det A$ is invertible (Many people would say "is a unit") in $R$.

Answer 3

Your context strongly suggests that $A \in \mathbb{R}^{m \times n}$ so that $A^T A \in \mathbb{R}^{n \times n}$. Our objective is to determine necessary and sufficient conditions that ensure that $A^TA$ is nonsingular. Let $N(A)$ denote the null space of of $A$, i.e., $$N(A) = \{ x \in \mathbb{R}^n \: : \: Ax = 0\}.$$ We shall now provide the standard proof of the fact that $$N(A) = N(A^TA).$$ If $x \in N(A)$, then $Ax = 0$ and $A^T A x = 0$. This shows that $N(A) \subseteq N(A^TA)$. If $x \in N(A^TA)$, then $A^TAx = 0$ which implies $0 = x^T A^T A x = \|Ax\|_2^2$. This shows that $x \in N(A)$ and $N(A^TA) \subseteq N(A)$. This completes the proof. We can now conclude that $A^TA$ is nonsingular iff $N(A) = 0$ iff the columns of $A$ are linearly independent.

In your context of linear regression it is exceedingly likely $m \ge n$ and that you are trying to solve a linear system $$Ax = b$$ in the least squares sense. You are advised not to solve the system of normal equations $$A^TA x = A^Tb.$$ In exact arithmetic the two problems are equivalent, but the system of normal equations is more sensitive to rounding errors than the original problem. A far better strategy is to compute a $QR$ factorization of $A$, i.e., $$A = QR$$ where $Q \in \mathbb{R}^{m \times n}$ is orthogonal and $R \in \mathbb{R}^{n \times n}$ is upper triangular. You can do this using the modified Gram-Schmidt algorithm or the Householder QR factorization or you can use Givens rotations. You will find that $$N(R) = N(A).$$ You can therefore expect to solve $Rx = Q^T b$ using backward substitution. In the absence of user stupidity, we certainly expect that $$N(A) = \{0\},$$ but if you are not confident about the people who constructed the matrix $A$ or if any mistakes will have real-life consequences, then you compute a rank-revealing QR factorization of $A$, i.e., $$A\Pi = QR$$ where $\Pi$ is permutation matrix. This process will reveal if $A$ is close to matrix that does not have full rank. All the algorithms that I have mentioned are discussed in detail in the book "Matrix Computations" by Charles van Loan and Gene Golub.