Matrix normal forms
This page collects functionality for transforming matrices into normal forms or related decompositions. Some algorithms also return transformation matrices which certify the result.
LU factorisation
LinearAlgebra.lu — Method
lu(A::MatrixElem{T}, P = SymmetricGroup(nrows(A))) where {T <: FieldElement}Return the LU decomposition of $A$.
More precisely, return a tuple $r, p, L, U$ consisting of the rank $r$ of $A$, a permutation $p$ belonging to $P$, a lower triangular matrix $L$ and an upper triangular matrix $U$ such that $p(A) = LU$. Here $p(A)$ denotes the matrix obtained by applying the permutation $p$ to the rows of $A$.
Examples
julia> M = matrix(QQ, 3, 3, [1 2 3; 4 5 6; 0 0 1])
[1//1 2//1 3//1]
[4//1 5//1 6//1]
[0//1 0//1 1//1]
julia> r, p, L, U = lu(M)
(3, (), [1 0 0; 4 1 0; 0 0 1], [1 2 3; 0 -3 -6; 0 0 1])AbstractAlgebra.fflu — Method
fflu(A::MatrixElem{T}, P = SymmetricGroup(nrows(A))) where {T <: RingElement}Return the fraction-free LU decomposition of $A$.
More precisely, return a tuple $r, d, p, L, U$ consisting of the rank $r$ of $A$, a denominator $d$, a permutation $p$ belonging to $P$, a lower triangular matrix $L$ and an upper triangular matrix $U$ such that $p(A) = LDU$. Here $p(A)$ denotes the matrix obtained by applying the permutation $p$ to the rows of $A$.
The matrix $D$ is the diagonal matrix $\operatorname{diag}(p_1, p_1p_2, \ldots, p_{n-2}p_{n-1}, p_{n-1}p_n)$, where the $p_i$ are the inverses of the diagonal entries of $L$.
The denominator $d$ is set to $\pm \det(S)$, where $S$ is an appropriate submatrix of $A$; if $A$ is square and nonsingular, then $S = A$. The sign is determined by the parity of the permutation.
Examples
julia> M = matrix(QQ, 3, 3, [1 2 3; 4 5 6; 0 0 1])
[1//1 2//1 3//1]
[4//1 5//1 6//1]
[0//1 0//1 1//1]
julia> r, d, p, L, U = fflu(M)
(3, -3//1, (), [1 0 0; 4 -3 0; 0 0 -3], [1 2 3; 0 -3 -6; 0 0 -3])Reduced row-echelon form
AbstractAlgebra.rref_rational — Method
rref_rational(M::MatrixElem{T}) where {T <: RingElement}Return the reduced row echelon form of $M$ using fraction-free arithmetic.
More precisely, return a tuple $r, A, d$ consisting of the rank $r$ of $M$, a matrix $A$ and a denominator $d$ in the base ring of $M$ such that $A/d$ is the reduced row echelon form of $M$.
Note that the denominator $d$ is not necessarily minimal.
Examples
julia> M = matrix(ZZ, 3, 3, [1 2 3; 4 5 6; 0 0 1])
[1 2 3]
[4 5 6]
[0 0 1]
julia> r, A, d = rref_rational(M)
(3, [-3 0 0; 0 -3 0; 0 0 -3], -3)
julia> is_rref(A)
true
julia> A/d
[1 0 0]
[0 1 0]
[0 0 1]AbstractAlgebra.rref — Method
rref(M::MatrixElem{T}) where {T <: FieldElement}Return the reduced row echelon form of $M$.
More precisely, return a tuple $r, A$ consisting of the rank $r$ of $M$ and the reduced row echelon form $A$ of $M$.
Examples
julia> M = matrix(QQ, 3, 3, [1 2 3; 4 5 6; 0 0 1])
[1//1 2//1 3//1]
[4//1 5//1 6//1]
[0//1 0//1 1//1]
julia> r, A = rref(M)
(3, [1 0 0; 0 1 0; 0 0 1])
julia> is_rref(A)
trueHessenberg form and similarity transformations
LinearAlgebra.hessenberg — Method
hessenberg(A::MatElem{T}) where {T <: RingElement}Return the Hessenberg form of $A$, i.e. an upper Hessenberg matrix which is similar to $A$.
An upper Hessenberg matrix has zero entries below the first subdiagonal.
Examples
julia> R, = residue_ring(ZZ, 7);
julia> M = matrix(R, 4, 4, [1 2 4 3; 2 5 1 0; 6 1 3 2; 1 1 3 5])
[1 2 4 3]
[2 5 1 0]
[6 1 3 2]
[1 1 3 5]
julia> H = hessenberg(M)
[1 5 5 3]
[2 1 1 0]
[0 1 3 2]
[0 0 2 2]
julia> is_hessenberg(H)
trueAbstractAlgebra.similarity! — Method
similarity!(A::MatrixElem{T}, r::Int, d::T) where {T <: RingElement}Apply a similarity transformation to the square matrix $A$ in-place.
Let $P$ be the identity matrix with all off-diagonal entries in row $r$ replaced by $d$. This function replaces $A$ by $P^{-1}AP$.
Similarity transformations preserve the minimal and characteristic polynomials of a matrix.
Examples
julia> R, = residue_ring(ZZ, 7);
julia> S = matrix_space(R, 4, 4)
Matrix space of 4 rows and 4 columns
over residue ring of integers modulo 7
julia> M = S([R(1) R(2) R(4) R(3); R(2) R(5) R(1) R(0);
R(6) R(1) R(3) R(2); R(1) R(1) R(3) R(5)])
[1 2 4 3]
[2 5 1 0]
[6 1 3 2]
[1 1 3 5]
julia> similarity!(M, 1, R(3))Hermite normal form
AbstractAlgebra.hnf — Method
hnf(A::MatElem{T}) where {T <: RingElement}Return the upper right row Hermite normal form of $A$.
The Hermite normal form is a canonical form for matrices. It is obtained by employing elementary row operations to produce an upper triangular matrix.
Examples
julia> A = matrix(ZZ, [2 3 -1; 3 5 7; 11 1 12])
[ 2 3 -1]
[ 3 5 7]
[11 1 12]
julia> H = hnf(A)
[1 0 255]
[0 1 17]
[0 0 281]
julia> is_hnf(H)
trueAbstractAlgebra.hnf_with_transform — Method
hnf_with_transform(A::MatElem{T}) where {T <: RingElement}Return the upper right row Hermite normal form of $A$, together with a transformation matrix.
More precisely, return a tuple $H, U$ where $H$ is the upper right row Hermite normal form of $A$ and $U$ is an invertible matrix such that $UA = H$.
Examples
julia> A = matrix(ZZ, [2 3 -1; 3 5 7; 11 1 12])
[ 2 3 -1]
[ 3 5 7]
[11 1 12]
julia> H, U = hnf_with_transform(A)
([1 0 255; 0 1 17; 0 0 281], [-47 28 1; -3 2 0; -52 31 1])
julia> U*A == H
trueSmith normal form
AbstractAlgebra.snf — Method
snf(A::MatElem{T}) where {T <: RingElement}Return the Smith normal form of $A$.
The Smith normal form is a canonical diagonal form obtained by applying invertible row and column transformations.
Examples
julia> A = matrix(ZZ, [2 3 -1; 3 5 7; 11 1 12])
[ 2 3 -1]
[ 3 5 7]
[11 1 12]
julia> S = snf(A)
[1 0 0]
[0 1 0]
[0 0 281]
julia> is_snf(S)
trueAbstractAlgebra.snf_with_transform — Method
snf_with_transform(A::MatElem{T}) where {T <: RingElement}Return the Smith normal form of $A$, together with transformation matrices.
More precisely, return a tuple $S, T, U$ where $S$ is the Smith normal form of $A$ and $T$ and $U$ are invertible matrices such that $TAU = S$.
Examples
julia> A = matrix(ZZ, [2 3 -1; 3 5 7; 11 1 12])
[ 2 3 -1]
[ 3 5 7]
[11 1 12]
julia> S, T, U = snf_with_transform(A)
([1 0 0; 0 1 0; 0 0 281], [1 0 0; 7 1 0; 229 31 1], [0 -3 26; 0 2 -17; -1 0 1])
julia> T*A*U == S
truePopov forms
AbstractAlgebra.weak_popov — Method
weak_popov(A::MatElem{T}) where {T <: PolyRingElem}Return the weak Popov form of $A$.
The matrix $A$ must have entries in a univariate polynomial ring over a field. The weak Popov form is a row-reduced matrix, in which the nonzero rows have distinct leading positions with respect to their degrees.
Examples
julia> R, x = polynomial_ring(QQ, :x);
julia> A = matrix(R, map(R, Any[1 2 3 x; x 2*x 3*x x^2; x x^2+1 x^3+x^2 x^4+x^2+1]))
[1 2 3 x]
[x 2*x 3*x x^2]
[x x^2 + 1 x^3 + x^2 x^4 + x^2 + 1]
julia> P = weak_popov(A)
[ 1 2 3 x]
[ 0 0 0 0]
[-x^3 -2*x^3 + x^2 - 2*x + 1 -2*x^3 + x^2 - 3*x 1]AbstractAlgebra.weak_popov_with_transform — Method
weak_popov_with_transform(A::MatElem{T}) where {T <: PolyRingElem}Return the weak Popov form of $A$, together with a transformation matrix.
The matrix $A$ must have entries in a univariate polynomial ring over a field. The weak Popov form is a row-reduced form in which the nonzero rows have distinct leading positions determined by their degrees.
More precisely, return a tuple $P, U$ where $P$ is the weak Popov form of $A$ and $U$ is a transformation matrix such that $P = UA$.
Examples
julia> R, x = polynomial_ring(QQ, :x);
julia> A = matrix(R, map(R, Any[1 2 3 x; x 2*x 3*x x^2; x x^2+1 x^3+x^2 x^4+x^2+1]))
[1 2 3 x]
[x 2*x 3*x x^2]
[x x^2 + 1 x^3 + x^2 x^4 + x^2 + 1]
julia> P, U = weak_popov_with_transform(A)
([1 2 3 x; 0 0 0 0; -x^3 -2*x^3+x^2-2*x+1 -2*x^3+x^2-3*x 1], [1 0 0; -x 1 0; -x^3-x 0 1])
julia> U*A == P
trueAbstractAlgebra.popov — Method
popov(A::MatElem{T}) where {T <: PolyRingElem}Return the Popov form of $A$.
The matrix $A$ must have entries in a univariate polynomial ring over a field. The Popov form is a canonical row-reduced form. It is a weak Popov form satisfying additional normalization conditions on the leading entries.
Examples
julia> R, x = polynomial_ring(QQ, :x);
julia> A = matrix(R, map(R, Any[1 2 3 x; x 2*x 3*x x^2; x x^2+1 x^3+x^2 x^4+x^2+1]))
[1 2 3 x]
[x 2*x 3*x x^2]
[x x^2 + 1 x^3 + x^2 x^4 + x^2 + 1]
julia> P = popov(A)
[ 0 0 0 0]
[ 1 2 3 x]
[1//2*x^3 x^3 - 1//2*x^2 + x - 1//2 x^3 - 1//2*x^2 + 3//2*x -1//2]AbstractAlgebra.popov_with_transform — Method
popov_with_transform(A::MatElem{T}) where {T <: PolyRingElem}Return the Popov form of $A$, together with a transformation matrix.
The matrix $A$ must have entries in a univariate polynomial ring over a field. The Popov form is a canonical row-reduced form. It is a weak Popov form satisfying additional normalization conditions on the leading entries.
More precisely, return a tuple $P, U$ where $P$ is the Popov form of $A$ and $U$ is a transformation matrix such that $P = UA$.
Examples
julia> R, x = polynomial_ring(QQ, :x);
julia> A = matrix(R, map(R, Any[1 2 3 x; x 2*x 3*x x^2; x x^2+1 x^3+x^2 x^4+x^2+1]))
[1 2 3 x]
[x 2*x 3*x x^2]
[x x^2 + 1 x^3 + x^2 x^4 + x^2 + 1]
julia> P, U = popov_with_transform(A)
([0 0 0 0; 1 2 3 x; 1//2*x^3 x^3-1//2*x^2+x-1//2 x^3-1//2*x^2+3//2*x -1//2], [-x 1 0; 1 0 0; 1//2*x^3+1//2*x 0 -1//2])
julia> U*A == P
true