Rank of matrix on Z2 field

Hi

Suppose I have a symmetric matrix defined on the Z2 field {0,1}. I want to calculate its rank. Do we have any function to do this? Thanks

Look at the Nemo and AbstractAlgebra packages:
https://nemocas.github.io/Nemo.jl/dev/residue/

There is a rank function in AbstractAlgebra.

Hi

I find a rank function in AbstractAlgebra.jl. But I still don’t know how to use it. I guess this is partially due to my ignorance about abstract algebra. Could you please give me more hints? Thanks

1 Like

Boolean algebra is already Z2. You could just use LinearAlbegra.rank on a Matrix{Bool}.

For example

julia> rank([true false
             true true])
2

julia> rank([true true
             true true])
1
1 Like

Oh this is what I want. Thanks.

Hi Mason:

One more question is if my matrix dimension is large, will the result be inaccurate? Also, do you know the time complexity of using rank on a matrix of Boolean variables.

Thanks

Hm, the rank is determined via the singular value decomposition and it does this by promoting everything to Float64 so I’m not sure how well this will actually preserve the Z2 properties you’re after. I think it’s fine but I’m not sure.

Accuracy can be controlled via the tolerance keywords, and the time complexity is just the regular SVD time complexity.

1 Like

Maybe check out GitHub - scheinerman/LinearAlgebraX.jl: Exact linear algebra functions. This is pretty slick. You can make a matrix of Mod{2} values and then use rankx for an exact rank. Probably has worse time complexity than floats, maybe worth testing.

There was a previous discussion and example given here:

1 Like

Hi Mason. In fact I am worried that transferring bools to Float64 and doing SVD will lead to problems. I guess what James posted shows this issue. Let me try the function rankx instead.

1 Like

Here is an example using Nemo; first define the field \mathbb{Z}_2:

using Nemo
Z2 = ResidueRing(ZZ, 2)

For purposes of the example, create a random base matrix, e.g.
X = rand([0,1], 4,5)
or define one:

X = [
 0  1  1  0  1
 1  0  1  1  0
 0  1  1  1  1
 0  1  1  0  1
]

then convert it into a Nemo object in the field (residue ring) \mathbb{Z}_2

A = matrix(Z2, X)

Then call rank:

julia> rank(A)
3
2 Likes

Oh I got it. Thanks.

No rank does depend on the field over which you consider the matrix for instance:

julia> using LinearAlgebra

julia> A = [1 0 1; 0 1 1; 1 1 0]
3×3 Matrix{Int64}:
 1  0  1
 0  1  1
 1  1  0

julia> det(A)
-2.0

What does it tell us? This matrix is invertible over the reals since its deteminant is nonzero. But over Z/2 its determinant is zero so it is not invertible. So over one field it has full rank and over the other it does not have full rank.

2 Likes