# Does $A^TA$ always result in a square matrix?

And does the resulting $$A^TA$$ matrix always have an inverse to solve for $$\vec{w}$$ in

$$A^TA\vec{w}=A^T\vec{t}$$ ?

• it is always a square, and always positive semidefinite. The rank is the same as that of $A,$ so if rank of $A$ is maximal ( the smaller dimension, columns or rows) it all works out Jun 1, 2019 at 2:17
• The right hand side of that equation should be $A^T \vec{t}$. Jun 1, 2019 at 2:18
• @littleO thanks fixed Jun 1, 2019 at 2:21
• The matrix is always square, but it need not be invertible. Easy counterexample: $A = 0$. Jun 1, 2019 at 2:31
• @TheoBendit If $A^TA$ is not invertible then how do we solve for $\vec{w}$? Jun 1, 2019 at 3:15

As I said in the comments, $$A^\top A$$ is always square (Shogun covers this in more detail in their answer). However, $$A^\top A$$ may not have an inverse, particularly if the rank of $$A$$ does not match the number of columns of $$A$$, or equivalently, the columns are linearly dependent (which will always happen when $$A$$ has more columns than rows).

To answer the follow-up question in the comments (properly), you solve the matrix equation $$A^\top A \vec{w} = A^\top \vec{t}$$. This is done with Gauss-Jordan elimination.

Let's do an example to illustrate this. Take $$A = \begin{pmatrix} 1 & 2 & -1 \\ 0 & -1 & 1 \\ 2 & -1 & 3 \\ -1 & 1 & -2 \end{pmatrix}.$$ First, note that the second column plus the first column is the first column, and hence the columns are linearly dependent. I therefore expect $$A^\top A%$$ to be a rank two $$3 \times 3$$ matrix, which will make it singular. Computing, $$A^\top A = \begin{pmatrix}1 & 0 & 2 & -1 \\ 2 & -1 & -1 & 1 \\ -1 & 1 & 3 & -2 \end{pmatrix}\begin{pmatrix} 1 & 2 & -1 \\ 0 & -1 & 1 \\ 2 & -1 & 3 \\ -1 & 1 & -2 \end{pmatrix} = \begin{pmatrix} 6 & -1 & 7 \\ -1 & 7 & -8 \\ 7 & -8 & 15 \end{pmatrix}.$$ This matrix is indeed singular, as (again, not coincidentally) the second and third columns add to give the first column (or compute the determinant).

We use this when taking a vector $$\vec{t} \in \Bbb{R}^4$$ and finding a vector $$\vec{y}$$ in the columnspace of $$A$$ that is closest (in the usual Euclidean $$2$$-norm) to $$\vec{t}$$. Let's take $$\vec{t} = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}.$$ We can see that $$\vec{t}$$ does not already belong to this columnspace by solving $$A \vec{x} = \vec{t}$$ and obtaining no solution. In this case, we would solve $$\begin{pmatrix} 1 & 2 & -1 \\ 0 & -1 & 1 \\ 2 & -1 & 3 \\ -1 & 1 & -2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix},$$ which as an augmented matrix comes to \begin{align*} \left(\begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & -1 & 1 & 1 \\ 2 & -1 & 3 & 1 \\ -1 & 1 & -2 & 1 \end{array}\right) &\sim \left(\begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & -1 & 1 & 1 \\ 0 & -5 & 5 & -1 \\ 0 & 3 & -3 & 2 \end{array}\right) \\ &\sim \left(\begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & 0 & -6 \\ \color{red}0 & \color{red}0 & \color{red}0 & \color{red}5 \end{array}\right). \end{align*} The system is inconsistent, so indeed, $$\vec{t}$$ is not in the columnspace of $$A$$. However, we can multiply $$A^\top$$ to $$\vec{t}$$ to get $$\begin{pmatrix}1 & 0 & 2 & -1 \\ 2 & -1 & -1 & 1 \\ -1 & 1 & 3 & -2 \end{pmatrix}\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2 \\ 1 \\ 1 \end{pmatrix}.$$ Our normal equation becomes $$\begin{pmatrix} 6 & -1 & 7 \\ -1 & 7 & -8 \\ 7 & -8 & 15 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 2 \\ 1 \\ 1 \end{pmatrix},$$ or as an augmented matrix, \begin{align*} \left(\begin{array}{ccc|c} 6 & -1 & 7 & 2 \\ -1 & 7 & -8 & 1 \\ 7 & -8 & 15 & 1 \end{array}\right) &\sim \left(\begin{array}{ccc|c} 1 & -7 & 8 & -1 \\ 6 & -1 & 7 & 2 \\ 7 & -8 & 15 & 1 \end{array}\right) \\ &\sim \left(\begin{array}{ccc|c} 1 & -7 & 8 & -1 \\ 0 & 41 & -41 & 8 \\ 0 & 41 & -41 & 8 \end{array}\right) \\ &\sim \left(\begin{array}{ccc|c} 1 & -7 & 8 & -1 \\ 0 & 1 & -1 & \frac{8}{41} \\ 0 & 0 & 0 & 0 \end{array}\right) \\ &\sim \left(\begin{array}{ccc|c} 1 & 0 & \color{red}1 & \frac{15}{41} \\ 0 & 1 & \color{red}{-1} & \frac{8}{41} \\ 0 & 0 & \color{red}0 & 0 \end{array}\right) \end{align*} Note that, as we always expect from the normal equation, we have consistency; there is no zero row with a non-zero augmented number. That is, we have a solution. Since $$A^\top A$$ is not invertible, we have a column without a pivot, which gives us a free variable. Since it occurs in the third column, $$x_3$$ is a good candidate to assign as a free variable.

Let $$t = x_3$$. We have from the first row, $$x_1 + x_3 = \frac{15}{41}$$, so $$x_1 = -t + \frac{15}{41}$$. From the second row, $$x_2 - x_3 = \frac{8}{41}$$, so $$x_2 = t + \frac{8}{41}$$.

Now, the actual point $$\vec{y}$$ that is closest to $$\vec{t}$$ from the columnspace of $$A$$ is given by $$A \vec{x}$$, where $$\vec{x}$$ is one of the above solution. It doesn't matter which; just pick any value of $$t$$ you want ($$t = 0$$ is usually easy). However, I'm going to leave $$t$$ arbitrary just to demonstrate how it doesn't matter. We have \begin{align*} \vec{y} &= A \vec{x} = \begin{pmatrix} 1 & 2 & -1 \\ 0 & -1 & 1 \\ 2 & -1 & 3 \\ -1 & 1 & -2 \end{pmatrix}\begin{pmatrix} -t + \frac{15}{41} \\ t + \frac{8}{41} \\ t \end{pmatrix} \\ &= \begin{pmatrix} 1(-t + \frac{15}{41}) + 2(t + \frac{8}{41}) - 1t \\ 0(-t + \frac{15}{41}) + -1(t + \frac{8}{41}) + 1t \\ 2(-t + \frac{15}{41}) - 1(t + \frac{8}{41}) + 3t \\ -1(-t + \frac{15}{41}) + 1(t + \frac{8}{41}) - 2t \end{pmatrix} \\ &= \begin{pmatrix} \frac{31}{41} \\ -\frac{8}{41} \\ \frac{22}{41} \\ -\frac{7}{41} \end{pmatrix}. \end{align*} That is, the result of the least squares doesn't depend on $$t$$, i.e. it doesn't depend on your choice of vector from the normal equation. Solving via Gauss-Jordan elimination, then arbitrarily picking a solution, will obtain you to the same unique minimiser for the least squares problem.

Yes it is always square.

Consider $$A$$ be a $$m\times n$$ matrix. The dimensions of $$A^T$$ will be $$n \times m$$

Hence $$A^TA$$ will have dimensions $$n \times n$$ which is clearly a square matrix.

However in some cases when $$A=0$$ we cannot find a inverse.

It's always square.If $$A \in \mathbb{R}^{n \times m}$$ then $$A^{T} \in \mathbb{R}^{m \times n}$$ so $$A^{T}A \in \mathbb{R}^{m \times m}$$

The inverse will only exist if $$A$$ is full rank since $$\textrm{Rank}(A) = \textrm{Rank}(A^{T}A)$$

However the minimum norm solution to $$\|Ax - b\|^{2}$$ is given by the solution to $$A^{T}Ax = A^{T}b$$ which is called the normal equations. Not a good method of solving it directly though since $$\kappa(A^{T}A) = \kappa(A)^{2}$$