3
$\begingroup$

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}$?

and

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.

$\endgroup$

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.