# How to enumerate the generalised inverse of given matrix?

Let $A$ be a given singular matrix over a finite field. Then how to enumerate the solutions of the system of equation

$$Ax=b, b \in R(A), \text{range of } A$$

Since, $A$ is singular matrix I can find the generalized inverse $G$ (i.e., AGA=A) of $A$ . Note that, $Gb$ is one of the solution. And so the set of all solution can be written as $${Gb+(I-GA)u: u \text{ is arbitrary }}$$

Now, how to incorporate these ideas in sagemath?

I am a newbie to sagemath. So, the answerers kindly give me with the details.

edit retag close merge delete

Sort by ยป oldest newest most voted

There is an important mathematical notion for dealing with such problems : the kernel of a matrix, and i strongly suggest you to learn about it. If $K$ is the (right) kernel of $A$, if $x_0$ is a solution of the equation $Ax=b$, then the set of solutions of the equation is the set $x_0+K = \{x_0+k \mid k \in K\}$.

So, you can do the following:

Setting:

sage: A = random_matrix(GF(3),4,6) ; A
[2 1 2 2 0 2]
[2 2 0 1 2 0]
[0 2 2 1 2 2]
[2 0 0 1 0 2]
sage: b = vector(GF(3),(2,2,0,2)) ; b
(2, 2, 0, 2)


Find parameters $x_0$ and $K$:

sage: x0 = A.solve_right(b)
sage: x0
(1, 0, 0, 0, 0, 0)

sage: K = A.right_kernel() ; K
Vector space of degree 6 and dimension 2 over Finite Field of size 3
Basis matrix:
[1 0 1 1 0 0]
[0 1 2 1 0 1]


Enumerate solutions:

sage: solutions = [x0 + k for k in K] ; solutions
[(1, 0, 0, 0, 0, 0),
(2, 0, 1, 1, 0, 0),
(0, 0, 2, 2, 0, 0),
(1, 1, 2, 1, 0, 1),
(2, 1, 0, 2, 0, 1),
(0, 1, 1, 0, 0, 1),
(1, 2, 1, 2, 0, 2),
(2, 2, 2, 0, 0, 2),
(0, 2, 0, 1, 0, 2)]


You can check:

sage: for i in solutions:
....:     print A*i
(2, 2, 0, 2)
(2, 2, 0, 2)
(2, 2, 0, 2)
(2, 2, 0, 2)
(2, 2, 0, 2)
(2, 2, 0, 2)
(2, 2, 0, 2)
(2, 2, 0, 2)
(2, 2, 0, 2)

more