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

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