Consider the following matrix
$ A = \begin{bmatrix} 0 & 4 & 4 \\
1 & 1 & 1 \\
4 & 0 & 4 \\
4 & 4 & 0 \\
1 & 1 & 1
\end{bmatrix}$ over $\mathbb{F}_5^{5 \times 3}$.
This matrix has full column rank (rank = 3). When I compute the left inverse, the matrix $A^TA$ is computed to be
$A^TA = \begin{bmatrix} 4 & 3 & 3 \\
3 & 4 & 3 \\
3 & 3 & 4 \end{bmatrix}$
This matrix has determinant 0 (and rank 2) and naturally the inverse doesn't exist. So computation of $(A^TA)^{-1}A^T$ is not possible.
Can someone explain to me why even after A having a full column rank failed to have a left inverse?
Added question: The same matrix $A$ when considered over $\mathbb{R}$ (or $\mathbb{Q}$) does have a left inverse. So is the condition for the existence of left (or right) inverse different for matrices over finite fields?
Best Answer
It does have a left inverse. $$\begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 4 & 4 & 4 & 0 & 0 \end{pmatrix}$$
The usual proof Why is $A^TA$ invertible if $A$ has independent columns? that $A^TA$ is invertible uses dot products. But dot products don't have good properties over finite fields, because it is possible that $\langle x, x\rangle = 0$ when $x \ne 0$. The columns of $A^TA$ in your example all have this property.