Let $M$ be a $k\times n$ matrix with $k < n$, and assume that $\text{rank}(M)=k$.

Over $\mathbb{R}$, one can compute a right inverse of $M$ as follows:

$$M_\text{right}^{-1} = M^T(MM^T)^{-1}$$

However, the above relation does not necessarily hold over finite fields. For instance, let $M=\begin{bmatrix}1&2\end{bmatrix}$ be defined over $GF(5)$. Then, $MM^T=\begin{bmatrix}0\end{bmatrix}$, which is not invertible, so $(MM^T)^{-1}$ is not defined over this field.

The right inverse can basically be computed by solving a linear system over the finite field. In the example above, let $M_\text{right}^{-1}=\begin{bmatrix}a\\b\end{bmatrix}$. Then:

$$M M_\text{right}^{-1} = I \qquad\Rightarrow\qquad a+2b=1 \qquad\Rightarrow\qquad a=1-2b$$

Therefore, we can enumerate all right inverses over $GF(5)$:

$\begin{bmatrix}1\\0\end{bmatrix}, \begin{bmatrix}4\\1\end{bmatrix},\begin{bmatrix}2\\2\end{bmatrix},\begin{bmatrix}0\\3\end{bmatrix},\begin{bmatrix}3\\4\end{bmatrix}$

Is there a better way to compute the right inverse of a matrix over finite fields, such as the closed formula $M_\text{right}^{-1} = M^T(MM^T)^{-1}$ over $\mathbb{R}$?


Can we build something similar to the Moore–Penrose pseudoinverse for finite fields?

Edit: This paper by John D. Fulton discusses generalized inverses of matrices over a finite field, which seems to be relevant to my second question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.