How can we calculate the rank of a large circular matrix over GF(2) efficiently ? for instance ( 10^6* 10^6 matrix ) ( Best algorithm )
Asked
Active
Viewed 61 times
0
-
$10^6$ is a relatively small number. The ordinary Gauss-Jordan method should work. – markvs Oct 06 '20 at 21:11
-
Any usefull link to the ordinary Gauss-Jordn method – meh98 Oct 06 '20 at 21:13
-
Here you can find a faster method using Fourier transform (see the Applications section). It also has a link to Gaussian reduction. – markvs Oct 06 '20 at 21:17
-
could you give me the link of the two methods ? ( where 's the application section ? ) – meh98 Oct 06 '20 at 21:19
-
Sorry! Here it is: https://en.wikipedia.org/wiki/Circulant_matrix – markvs Oct 06 '20 at 21:27
-
By solving C*X=b with C the circulant matrix how can i find the rank ? – meh98 Oct 06 '20 at 21:33
-
Actually finding the rank is easier: look at the section Rank of the same text. – markvs Oct 06 '20 at 21:49