# Left inverse of a matrix with full rank

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?

• In general $\text{rank}(A^TA)\leq \text{rank}(A)$. In fields of characteristic zero this becomes equality, but the proof relies on looking positive definiteness of $\big \Vert Ax \big\Vert_2\geq 0$ which doesn't hold for finite fields. The problem with your computation is $A$ is injective and $A^T$ is surjective so in some sense you have the ordering backwards. if you looked at $AA^T$, you'd see that rank$(AA^T) =$ rank$(A) = 3$ but there isn't a reason for $AA^T$ and $A^TA$ to have the same rank ('comparable' characteristic polynomials isn't enough when you don't have spectral theorem). Jan 20, 2020 at 21:27
• to reinforce the point -- (i) in my above comment the transpose naturally should be interpreted as the conjugate transpose if for some reason the scalars were in $\mathbb C$. (ii) A simpler example using a finite field for the OP and @DietrichBurde to consider is $B := \left[\begin{matrix}1 & 0\\0 & 1\\1 & 0\\0 & 1\end{matrix}\right]$ with scalars in $\mathbb F_2$. Then $B$ has full column rank of 2 but $B^T B = \left[\begin{matrix}0 & 0\\0 & 0\end{matrix}\right]$, so $B^T B$ certainly isn't invertible. note: $0 = \text{rank} (B^T B) \lt \text{rank} (BB^T) = \text{rank} (B) = 2$ Jan 21, 2020 at 7:22

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.