0

I'm working on the Gaussian elimination being implemented on gf(2). I have successfully reduced my 286*286 matrix into rref. Now I need to find the null space of this(please tell me how to do this effectively as I'm going to hardcode this in java). It would be a great help is someone could give me the gist of finding basis and then solution of this. Also as a extra detail I'm doing all this as a part of my attempt to implement Quadratic Sieve in java.

Bernard
  • 175,478
DumpDaCode
  • 11
  • Do you mean $A\mathbf{x} = \mathbf{0}$? And what is gf(2)? – The Pointer Apr 06 '20 at 17:47
  • @ThePointer Yes Ax = 0. Gf(2) is galois field of 0 and 1. The matrix will only contain 0's and 1's. It utilizes 1-bit integer arithmetic instead. I'm stuck with solving this issue. Which in turn has been delaying the deadline for quadratic sieve implementation. – DumpDaCode Apr 06 '20 at 17:50
  • @ThePointer: I suppose it is $\mathbf F_2$ (gf is for Galois field). – Bernard Apr 06 '20 at 17:51
  • @rajiv You need to edit your question and make it clearer. – The Pointer Apr 06 '20 at 17:53
  • @Bernard Ahh, ok. This is outside of my scope of knowledge. – The Pointer Apr 06 '20 at 17:54
  • I don't see whare the problem is. Ultimately, the RREF is in the form of a block-diagonal matrix, where the blocks are either the $0$-matrix or a unit matrix. Therefore the unknowns corresponding to the non-zero blocks are $0$. – Bernard Apr 06 '20 at 18:00
  • @Bernard The way I'm approaching this basis of null space after rref. I'm checking the diagonal elements and if I found one that is none zero its being labeled as free variable. In this manner I'm generating an array of free variables. lets say N free variables. Out of this N variables I'm setting X free variable as 1 and rest as zero. By back substitution I'm getting a solution for this X free variable being set to one only. Is this the way to find null spaces? – DumpDaCode Apr 06 '20 at 18:07
  • I'm not sure I fully understand. What is a diagonal element which is ‘none zero’? – Bernard Apr 06 '20 at 18:25
  • @Bernard its a mistake from my part as i look at it now. I meant to say the one that is zero. Nevertheless is my approach correct? – DumpDaCode Apr 06 '20 at 18:29
  • You can find a purely mechanical method for extracting a kernel basis from the RREF described here. – amd Apr 06 '20 at 18:34
  • OK. If I understand well, you consider the list of variables corresponding to a diagonal $0$, which are free variables, and you consider the vectors which all coordinates $0$, but one in this list, to obtain a basis of the kernel? – Bernard Apr 06 '20 at 18:35
  • @Bernard yes. Is this correct? – DumpDaCode Apr 06 '20 at 18:36
  • For me, it is perfectly correct. – Bernard Apr 06 '20 at 18:41
  • @amd I went through that article. thank you! – DumpDaCode Apr 06 '20 at 18:48
  • If it answered your question, I’ll flag this one as a duplicate. – amd Apr 06 '20 at 18:50

0 Answers0