Modulo2.jl

Modulo2

This package provides types and functions for linear algebra modulo 2. It defines a type ZZ2 for integers mod 2 and ZZ2Array (ZZ2Vector, ZZ2Matrix) for arrays (vectors, matrices) with elements in ZZ2.

See also ZZ2, ZZ2Array.

ZZ2 <: Number

A type representing integers modulo 2.

Elements can be created via the functions zero and one or from an argument of type Bool or any other Integer type. More generally, any argument accepted by isodd can be converted to ZZ2. In algebraic computations with ZZ2, Integer types are promoted to ZZ2. Conversely, elements of type ZZ2 can be converted to Bool.

See also Base.zero, Base.one, Base.iszero, Base.isone, Base.isodd.

Examples

julia> ZZ2(1) == one(ZZ2)
true

julia> iszero(ZZ2(4.0))
true

julia> x = ZZ2(1) + 3
0

julia> typeof(x)
ZZ2

julia> Bool(x), convert(Bool, x)
(false, false)

count_zeros(a::ZZ2) -> Integer

Return 1 if a equals ZZ2(0) and 0 otherwise.

See also count_ones(::ZZ2), count_zeros(::ZZ2Array), count_zeros(::Integer).

count_ones(a::ZZ2) -> Integer

Return 1 if a equals ZZ2(1) and 0 otherwise.

See also count_zeros(::ZZ2), count_ones(::ZZ2Array), count_ones(::Integer).

ZZ2Vector <: AbstractVector{ZZ2}
ZZ2Matrix <: AbstractMatrix{ZZ2}
ZZ2Array{N} <: AbstractArray{ZZ2,N}

An abstract vector / matrix / array type with elements of type ZZ2.

The internal representation is packed, meaning that each element only uses one bit. However, columns are internally padded to a length that is a multiple of 256.

A ZZ2Array can be created from any AbstractArray whose elements can be converted to ZZ2. One can also leave the elements undefined by using the undef argument.

See also zeros, ones, zz2vector, resize!, det, inv, rank, rcef, rref.

Examples

julia> ZZ2Matrix([1 2 3; 4 5 6])
2×3 ZZ2Matrix:
 1  0  1
 0  1  0

julia> v = ZZ2Vector(undef, 2); v[1] = true; v[2] = 2.0; v
2-element ZZ2Vector:
 1
 0

resize!(a::ZZ2Vector, n::Integer) -> a

Change the length of a to n and return a. In case a is enlarged, the new entries are undefined.

zeros(ZZ2, ii::NTuple{N,Integer}) where N

Return a ZZ2Array of size ii with zero entries.

ones(ZZ2, ii::NTuple{N,Integer}) where N

Return a ZZ2Array of size ii with entries ZZ2(1).

count_zeros(a::ZZ2Array) -> Integer

Return the number of elements of a equal to ZZ2(0).

See also count_ones(::ZZ2Array), count_zeros(::ZZ2), count_zeros(::Integer).

count_ones(a::ZZ2Array) -> Integer

Return the number of elements of a equal to ZZ2(1).

See also count_zeros(::ZZ2Array), count_ones(::ZZ2), count_ones(::Integer).

zz2vector(n) -> ZZ2Vector

Return a ZZ2Vector containing the bit representation of n. Here n must be a Base.BitInteger or a bit integer defined by the package BitIntegers.jl.

See also zz2vector!, Base.BitInteger, BitIntegers.AbstractBitSigned, BitIntegers.AbstractBitUnsigned.

Example

julia> zz2vector(Int8(35))
8-element ZZ2Vector:
 1
 1
 0
 0
 0
 1
 0
 0

zz2vector!(a::ZZ2Vector, n) -> a

Fill a with the bit representation of n and return a. Here n must be a Base.BitInteger or a bit integer defined by the package BitIntegers.jl. The length of a is set to the bit length of n.

See also zz2vector, Base.BitInteger, BitIntegers.AbstractBitSigned, BitIntegers.AbstractBitUnsigned.

Modulo2.randomarray(ii...) -> ZZ2Array

Return a ZZ2Array of size ii with random entries.

mul!(c::ZZ2Vector, a::ZZ2Matrix, b::AbstractVector{<:Number}, α::Number = ZZ2(1), β::Number = ZZ2(0)) -> c

Store the combined matrix-vector multiply-add α a*b + β c in c and return c. With the default values of α and β the product a*b is computed. The elements of b as well as α and β must be convertible to ZZ2.

This function is re-exported from the module LinearAlgebra.

mul!(c::ZZ2Matrix, a::ZZ2Matrix, b::AbstractMatrix{<:Number}, α::Number = ZZ2(1), β::Number = ZZ2(0)) -> c

Store the combined matrix-matrix multiply-add α a*b + β c in c and return c. With the default values of α and β the product a*b is computed. The elements of b as well as α and β must be convertible to ZZ2.

This function is re-exported from the module LinearAlgebra.

rcef(b::ZZ2Matrix; reduced = true) -> ZZ2Matrix

Return the tuple (r, c) where r is the rank of the matrix b and c a column echelon form of it. If reduced is true, then the reduced column echelon form is computed.

See also rref, rcef!.

Examples

julia> a = ZZ2Matrix([1 0 0; 1 1 1])
2×3 ZZ2Matrix:
 1  0  0
 1  1  1

julia> rcef(a)
(2, ZZ2[1 0 0; 0 1 0])

julia> rcef(a; reduced = false)
(2, ZZ2[1 0 0; 1 1 0])

rcef!(b::ZZ2Matrix; reduced = true) -> ZZ2Matrix

Return the tuple (r, c) where r is the rank of the matrix b and c a column echelon form of it. If reduced is true, then the reduced column echelon form is computed. The argument b may be modified during the computation, which avoids the allocation of a new matrix.

See also rcef.

rref(b::ZZ2Matrix; reduced = true) -> ZZ2Matrix

Return the tuple (r, c) where r is the rank of the matrix b and c a row echelon form of it. If reduced is true, then the reduced row echelon form is computed.

Note that it is more efficient to compute a (reduced) column echelon form via rcef.

See also rcef.

Examples

julia> a = ZZ2Matrix([1 1; 0 1; 0 1])
3×2 ZZ2Matrix:
 1  1
 0  1
 0  1

julia> rref(a)
(2, ZZ2[1 0; 0 1; 0 0])

julia> rref(a; reduced = false)
(2, ZZ2[1 1; 0 1; 0 0])

rank(b::ZZ2Matrix) -> Int

Return the rank of the matrix b.

See also rank!.

rank!(b::ZZ2Matrix) -> Int

Return the rank of the matrix b. The argument b may be modified during the computation, which avoids the allocation of a new matrix.

See also rank.

det(b::ZZ2Matrix) -> ZZ2

Return the determinant of the matrix b.

See also det!.

det!(b::ZZ2Matrix) -> ZZ2

Return the determinant of the matrix b. The argument b may be modified during the computation, which avoids the allocation of a new matrix.

See also det.

inv(b::ZZ2Matrix) -> ZZ2Matrix

Return the inverse of the matrix b, which must be invertible.

See also inv!.

inv!(b::ZZ2Matrix) -> ZZ2Matrix

Return the inverse of the matrix b, which must be invertible. The argument b may be modified during the computation, which avoids the allocation of a new matrix.

See also inv.

Modulo2.zeropad!(a::ZZ2Array{N}) where N -> a

Set the padding bits in the underlying array a.data to zero and return a. The visible bits are not modified.

This is an internal function of the module.

Modulo2.gauss!(a::ZZ2Matrix, ::Val{mode}) where mode

• If mode == :rcef, return (r, b) where r is the rank of a and b its reduced column echelon form.
• If mode == :cef, return (r, b) where r is the rank of a and b a column echelon form of it.
• If mode == :det, return the determinant of a.
• If mode == :inv, return the inverse of a.

In all cases, the matrix a may be modified during the computation. This is an internal function of the module.