Rank of matrix on Z2 field

[jisutich]

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

[jd-foster]

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

There is a rank function in AbstractAlgebra.

[jisutich]

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

[Mason]

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

[jisutich]

Oh this is what I want. Thanks.

[jisutich]

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

[Mason]

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.

[Mason]

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.

[jd-foster]

There was a previous discussion and example given here:

Rank is wrong for Rational matrices

consider the matrix: julia> m=[1//(n+m) for n in 1:11, m in 1:11]; it can be inverted exactly with no problem: julia> one(m)==inv(m)*m true however: julia> rank(m) 10 The reason is that rank begins by converting its argument to floating-point. It seems to me that given a field (Rationals, but it could be rational fractions or any other field), the rank should be computed by computing the echelon form of the matrix rather that trying to convert to floats (which would not make sense for r…

[jisutich]

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.

[jd-foster]

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

[jisutich]

Oh I got it. Thanks.

[jw3126]

@Mason

I think it’s fine but I’m not sure.

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.