Enumerate all solutions to linear system over finite field

asked 2015-11-28 19:16:35 +0200

d125q
13 ●1 ●1 ●5

updated 2015-11-28 19:17:15 +0200

Assume I have a matrix $A$ and a vector $b$, both over some finite field $\mathrm{GF}(q)$. I would like to enumerate _all_ solutions to $A x = b$ (there are only finitely many).

I can generate a particular solution using A \ b and I can generate the nullspace of $A$ using A.right_kernel(), but how should I combine the two to enumerate all solutions?

edit retag flag offensive close merge delete

add a comment

1 Answer

Sort by » oldest newest most voted

answered 2015-11-28 19:36:54 +0200

d125q
13 ●1 ●1 ●5

updated 2015-11-28 19:37:10 +0200

Okay, I found the solution. Finite vector spaces support iteration, so one can simply do:

particular_soln = A.solve_right(b)
for homogeneous_soln in A.right_kernel():
    particular_soln + homogeneous_soln

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-11-28 19:16:35 +0200

Seen: 1,035 times

Last updated: Nov 28 '15

Enumerate all solutions to linear system over finite field edit

1 Answer