Similarity class types of matrices with entries in a finite field

The notion of a matrix conjugacy class type was introduced by J. A. Green in [Green55], in the context of computing the irreducible charcaters of finite general linear groups. The class types are equivalence classes of similarity classes of square matrices with entries in a finite field which, roughly speaking, have the same qualitative properties.

For example, all similarity classes of the same class type have centralizers of the same cardinality and the same degrees of elementary divisors. Qualitative properties of similarity classes such as semisimplicity and regularity descend to class types.

The most important feature of similarity class types is that, for any n, the number of similarity class types of n\times n matrices is independent of q. This makes it possible to perform many combinatorial calculations treating q as a formal variable.

In order to define similarity class types, recall that similarity classes of n\times n matrices with entries in \mathbf{F}_q correspond to functions

c: \mathrm{Irr}\mathbf{F}_q[t] \to \Lambda

such that

\sum_{f\in \mathrm{Irr}\mathbf{F}_q[t]} |c(f)|\deg f = n,

where we denote the set of irreducible monic polynomials in \mathbf{F}_q[t] by \mathrm{Irr}\mathbf{F}_q[t], the set of all partitions by \Lambda, and the size of \lambda \in \Lambda by |\lambda|.

Similarity classes indexed by functions c_1 and c_2 as above are said to be of the same type if there exists a degree-preserving self-bijection \sigma of \mathrm{Irr}\mathbf{F}_q[t] such that c_2 = c_1\circ \sigma. Thus, the type of c remembers only the degrees of the polynomials (and not the polynomials themselves) for which c takes a certain value \lambda. Replacing each irreducible polynomial of degree d for which c takes a non-trivial value \lambda by the pair (d, \lambda), we obtain a multiset of such pairs. Clearly, c_1 and c_2 have the same type if and only if these multisets are equal. Thus a similarity class type may be viewed as a multiset of pairs of the form (d, \lambda).

For 2 \times 2 matrices there are four types:

sage: for tau in SimilarityClassTypes(2):
....:    print tau
[[1, [1]], [1, [1]]]
[[1, [2]]]
[[1, [1, 1]]]
[[2, [1]]]

These four types correspond to the regular split semisimple matrices, the non-semisimple matrices, the central matrices and the irreducble matrices respectively.

For any matrix A in a given similarity class type, it is possible to calculate the number elements in the similarity class of A, the dimension of the algebra of matrices in M_n(A) that commite with A, and the cardinality of the subgroup of GL_n(\mathbf{F}_q) that commute with A. For each similarity class type, it is also possible to compute the number of classes of that type (and hence, the total number of matrices of that type). All these calculations treat the cardinality q of the finite field as a formal variable:

sage: M = SimilarityClassType([[1, [1]], [1, [1]]])
sage: M.class_card()
q^2 + q
sage: M.centralizer_algebra_dim()
2
sage: M.centralizer_group_card()
q^2 - 2*q + 1
sage: M.number_of_classes()
1/2*q^2 - 1/2*q
sage: M.number_of_matrices()
1/2*q^4 - 1/2*q^2

We now describe two applications of similarity class types.

We say that an n \times n matrix has rational canonical form type \lambda for some partition \lambda of n if the diagonal blocks in the rational canonical form have sizes given by the parts of \lambda. Thus the matrices with rational canonical type (n) are the regular ones, while the matrices with rational canonical type (1^n) are the central ones.

Using similarity class types, it becomes easy to get a formula for the number of matrices with a given rational canonical type:

sage: def matrices_with_rcf(la):
....:    return sum([tau.number_of_matrices() for tau in filter(lambda tau:tau.rcf()==la, SimilarityClassTypes(la.size()))])
sage: matrices_with_rcf(Partition([2,1]))
q^6 + q^5 + q^4 - q^3 - q^2 - q

Similarity class types can also be used to calculate the number of simultaneous similarity classes of k-tuples of n\times n matrices with entries in \mathbf{F}_q by using Burnside’s lemma:

sage: from sage.combinat.similarity_class_type import order_of_general_linear_group, centralizer_algebra_dim
sage: q = ZZ['q'].gen()
sage: def simultaneous_similarity_classes(n,k):
....:     return SimilarityClassTypes(n).sum(lambda la: q**(k*centralizer_algebra_dim(la)), invertible = True)/order_of_general_linear_group(n)
sage: simultaneous_similarity_classes(3, 2)
q^10 + q^8 + 2*q^7 + 2*q^6 + 2*q^5 + q^4

Similarity class types can be used to calculate the coefficients of generating functions coming from the cycle index type techniques of Kung and Stong (see Morrison [Morrison06]).

REFERENCES:

[Green55]Green, J. A. The characters of the finite general linear groups. Trans. Amer. Math. Soc. 80 (1955), 402–447. Available from: http://dx.doi.org/10.1090/S0002-9947-1955-0072878-2
[Morrison06]Morrison, Kent E. Integer sequences and matrices over finite fields. J. Integer Seq. 9 (2006), no. 2, Article 06.2.1, 28 pp. Available from: https://cs.uwaterloo.ca/journals/JIS/VOL9/Morrison/morrison37.html

AUTHOR:

  • Amritanshu Prasad (2013-07-18)
class sage.combinat.similarity_class_type.PrimarySimilarityClassType(parent, deg, par)

Bases: sage.structure.element.Element

A primary similarity class type is a pair consisting of a partition and a positive integer.

For a partition \lambda and a positive integer d, the primary similarity class type (d, \lambda) represents similarity classes of square matrices of order |\lambda| \cdot d with entries in a finite field of order q which correspond to the \mathbf{F}_q[t]-module

\frac{\mathbf{F}_q[t]}{p(t)^{\lambda_1} } \oplus
\frac{\mathbf{F}_q[t]}{p(t)^{\lambda_2}} \oplus \dotsb

for some irreducible polynomial p(t) of degree d.

centralizer_algebra_dim()

Return the dimension of the algebra of matrices which commute with a matrix of type self.

For a partition (d, \lambda) this dimension is given by d(\lambda_1 + 3\lambda_2 + 5\lambda_3 + \cdots).

EXAMPLES:

sage: PT = PrimarySimilarityClassType(2, [3, 2, 1])
sage: PT.centralizer_algebra_dim()
28
centralizer_group_card(q=None)

Return the cardinality of the centralizer group of a matrix of type self in a field of order q.

INPUT:

q – an integer or an indeterminate

EXAMPLES:

sage: PT = PrimarySimilarityClassType(1, [])
sage: PT.centralizer_group_card()
1
sage: PT = PrimarySimilarityClassType(2, [1, 1])
sage: PT.centralizer_group_card()
q^8 - q^6 - q^4 + q^2
degree()

Return degree of self.

EXAMPLES:

sage: PT = PrimarySimilarityClassType(2, [3, 2, 1])
sage: PT.degree()
2
partition()

Return partition corresponding to self.

EXAMPLES:

sage: PT = PrimarySimilarityClassType(2, [3, 2, 1])
sage: PT.partition()
[3, 2, 1]
size()

Return the size of self.

EXAMPLES:

sage: PT = PrimarySimilarityClassType(2, [3, 2, 1])
sage: PT.size()
12
statistic(func, q=None)

Return n_\lambda(q^d) where n_\lambda is the value returned by func upon input \lambda`, if ``self is (d, \lambda).

EXAMPLE:

sage: PT = PrimarySimilarityClassType(2, [3, 1])
sage: q = ZZ['q'].gen()
sage: PT.statistic(lambda la:q**la.size(), q = q)
q^8
class sage.combinat.similarity_class_type.PrimarySimilarityClassTypes(n, min)

Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation

All primary similarity class types of size n whose degree is greater than that of min or whose degree is that of min and whose partition is less than of min in lexicographic order.

A primary similarity class type of size n is a pair (\lambda, d) consisting of a partition \lambda and a positive integer d such that |\lambda|d = n.

INPUT:

  • n – a positive integer
  • min – a primary matrix type of size n.

EXAMPLES:

If min is not specified, then the class of all primary similarity class types of size n is created:

sage: PTC = PrimarySimilarityClassTypes(2)
sage: for PT in PTC:
....:     print PT
[1, [2]]
[1, [1, 1]]
[2, [1]]

If min is specified, then the class consists of only those primary similarity class types whose degree is greater than that of min or whose degree is that of min and whose partition is less than of min in lexicographic order:

sage: PTC = PrimarySimilarityClassTypes(2, min = PrimarySimilarityClassType(1, [1, 1]))
sage: for PT in PTC:
....:     print PT
[1, [1, 1]]
[2, [1]]
Element

alias of PrimarySimilarityClassType

size()

Return size of elements of self.

The size of a primary similarity class type (d, \lambda) is d |\lambda|.

EXAMPLES:

sage: PTC = PrimarySimilarityClassTypes(2)
sage: PTC.size()
2
class sage.combinat.similarity_class_type.SimilarityClassType(parent, tau)

Bases: sage.combinat.combinat.CombinatorialObject, sage.structure.element.Element

A similarity class type.

A matrix type is a multiset of primary similairty class types.

INPUT:

  • tau – A list of primary similarity class types

EXAMPLES:

sage: tau1 = SimilarityClassType([[3, [3, 2, 1]], [2, [2, 1]]]); tau1
[[2, [2, 1]], [3, [3, 2, 1]]]
as_partition_dictionary()

Return a dictionary whose keys are the partitions of types occuring in self and the value at the key \lambda is the partition formed by sorting the degrees of primary types with partition \lambda.

EXAMPLES:

sage: tau = SimilarityClassType([[1, [1]], [1, [1]]])
sage: tau.as_partition_dictionary()
{[1]: [1, 1]}
centralizer_algebra_dim()

Return the dimension of the algebra of matrices which commute with a matrix of type self.

EXAMPLES:

sage: tau = SimilarityClassType([[1, [1]], [1, [1]]])
sage: tau.centralizer_algebra_dim()
2
centralizer_group_card(q=None)

Return the cardinality of the group of matrices in GL_n(\mathbf{F}_q) which commute with a matrix of type self.

INPUT:

  • q – an integer or an indeterminate

EXAMPLES:

sage: tau = SimilarityClassType([[1, [1]], [1, [1]]])
sage: tau.centralizer_group_card()
q^2 - 2*q + 1
class_card(q=None)

Return the number of matrices in each similarity class of type self.

INPUT:

  • q – an integer or an indeterminate

EXAMPLES:

sage: tau = SimilarityClassType([[1, [1, 1, 1, 1]]])
sage: tau.class_card()
1
sage: tau = SimilarityClassType([[1, [1]], [1, [1]]])
sage: tau.class_card()
q^2 + q
is_regular()

Return True if every primary type in self has partition with one part.

EXAMPLES:

sage: tau = SimilarityClassType([[2, [1]], [1, [3]]])
sage: tau.is_regular()
True
sage: tau = SimilarityClassType([[2, [1, 1]], [1, [3]]])
sage: tau.is_regular()
False
is_semisimple()

Return True if every primary similarity class type in self has all parts equal to 1.

EXAMPLES:

sage: tau = SimilarityClassType([[2, [1, 1]], [1, [1]]])
sage: tau.is_semisimple()
True
sage: tau = SimilarityClassType([[2, [1, 1]], [1, [2]]])
sage: tau.is_semisimple()
False
number_of_classes(invertible=False, q=None)

Return the number of similarity classes of matrices of type self.

IMPUT:

  • invertible – Boolean; return number of invertible classes if set to True
  • q – An integer or an indeterminate

EXAMPLES:

sage: tau = SimilarityClassType([[1, [1]], [1, [1]]])
sage: tau.number_of_classes()
1/2*q^2 - 1/2*q
number_of_matrices(invertible=False, q=None)

Return the number of matrices of type self.

INPUT:

  • invertible – A boolean; return the number of invertible matrices if set

EXAMPLES:

sage: tau = SimilarityClassType([[1, [1]]])
sage: tau.number_of_matrices()
q
sage: tau.number_of_matrices(invertible = True)
q - 1
sage: tau = SimilarityClassType([[1, [1]], [1, [1]]])
sage: tau.number_of_matrices()
1/2*q^4 - 1/2*q^2
rcf()

Return the partition corresponding to the rational canonical form of a matrix of type self.

EXAMPLES:

sage: tau = SimilarityClassType([[2, [1, 1, 1]], [1, [3, 2]]])
sage: tau.rcf()
[5, 4, 2]
size()

Return the sum of the sizes of the primary parts of self.

EXAMPLES:

sage: tau = SimilarityClassType([[3, [3, 2, 1]], [2, [2, 1]]])
sage: tau.size()
24
statistic(func, q=None)

Return

prod_{(d, \lambda)\in       au} n_\lambda(q^d)

where n_\lambda(q) is the value returned by func on the input \lambda.

INPUT:

  • func – a function that takes a partition to a polynomial in q
  • q – an integer or an indeterminate

EXAMPLES:

sage: tau = SimilarityClassType([[1, [1]], [1, [2, 1]], [2, [1, 1]]])
sage: from sage.combinat.similarity_class_type import fq
sage: tau.statistic(lambda la: prod([fq(m) for m in la.to_exp()]))
(q^9 - 3*q^8 + 2*q^7 + 2*q^6 - 4*q^5 + 4*q^4 - 2*q^3 - 2*q^2 + 3*q - 1)/q^9
sage: q = ZZ['q'].gen()
sage: tau.statistic(lambda la: q**la.size(), q = q)
q^8
class sage.combinat.similarity_class_type.SimilarityClassTypes(n, min)

Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation

Class of all similarity class types of size n with all primary matrix types greater than or equal to the primary matrix type min.

A similarity class type is a multiset of primary matrix types.

INPUT:

  • n – a non-negative integer
  • min – a primary similarity class type

EXAMPLES:

If min is not specified, then the class of all matrix types of size n is constructed:

sage: M = SimilarityClassTypes(2)
sage: for tau in M:
....:     print tau
[[1, [1]], [1, [1]]]
[[1, [2]]]
[[1, [1, 1]]]
[[2, [1]]]

If min is specified, then the class consists of only those similarity class types which are multisets of primary matrix types which either have size greater than that of min, or if they have size equal to that of min, then they occur after min in the iterator for PrimarySimilarityClassTypes(n), where n is the size of min:

sage: M = SimilarityClassTypes(2, min = [1, [1, 1]])
sage: for tau in M:
....:     print tau
[[1, [1, 1]]]
[[2, [1]]]
Element

alias of SimilarityClassType

size()

Return size of self

EXAMPLES:

sage: tau = SimilarityClassType([[3, [3, 2, 1]], [2, [2, 1]]])
sage: tau.parent().size()
24
sum(stat, sumover='matrices', invertible=False, q=None)

Return the sum of a local statistic over all types.

Given a set of functions n_\lambda(q) (these could be polynomials or rational functions in q, for each similarity class type ` au` define

n_  au(q) = \prod_{(d,\lambda)\in   au} n_\lambda(q^d).

This function returns

\sum n_{    au(g)}(q)

where tau(g) denotes the type of a matrix g, and the sum is over all n  imes n matrices if sumover is set to “matrices”, is over all n  imes n similarity classes if sumover is set to “classes”, and over all n imes n types if sumover is set to types. If invertible is set to True, then the sum is only over invertible matrices or classes.

INPUT:

  • stat – a function which takes partitions and returns a function of q
  • sumover – a parameter, either “matrices”, “classes” or “types”
  • q – an integer or an indeterminate

OUTPUT:

A function of q.

EXAMPLES:

sage: M = SimilarityClassTypes(2)
sage: M.sum(lambda la:1)
q^4
sage: M.sum(lambda la:1, invertible = True)
q^4 - q^3 - q^2 + q
sage: M.sum(lambda la:1, sumover = "classes")
q^2 + q
sage: M.sum(lambda la:1, sumover = "classes", invertible = True)
q^2 - 1

Burside’s lemma can be used to calculate the number of similarity classes of matrices:

sage: from sage.combinat.similarity_class_type import centralizer_algebra_dim, order_of_general_linear_group
sage: q = ZZ['q'].gen()
sage: M.sum(lambda la:q**centralizer_algebra_dim(la), invertible = True)/order_of_general_linear_group(2)
q^2 + q
sage.combinat.similarity_class_type.centralizer_algebra_dim(la)

Return the dimension of the centralizer algebra in M_n(\mathbf{F}_q) of a nilpotent matrix whose Jordan blocks are given by la.

EXAMPLES:

sage: from sage.combinat.similarity_class_type import centralizer_algebra_dim
sage: centralizer_algebra_dim(Partition([2, 1]))
5

Note

If it is a list, la is expected to be sorted in decreasing order.

sage.combinat.similarity_class_type.centralizer_group_cardinality(la, q=None)

Return the cardinality of the centralizer group in GL_n(\mathbf{F}_q) of a nilpotent matrix whose Jordan blocks are given by la.

INPUT:

  • lambda – a partition
  • q – an integer or an indeterminate

OUTPUT:

A polynomial function of q.

EXAMPLES:

sage: from sage.combinat.similarity_class_type import centralizer_group_cardinality
sage: q = ZZ['q'].gen()
sage: centralizer_group_cardinality(Partition([2, 1]))
q^5 - 2*q^4 + q^3
sage.combinat.similarity_class_type.fq(n, q=None)

Return (1-q^{-1}) (1-q^{-2}) \cdots (1-q^{-n}).

INPUT:

  • n – A non-negative integer
  • q – an integer or an indeterminate

OUTPUT:

A rational function in q.

EXAMPLES:

sage: from sage.combinat.similarity_class_type import fq
sage: fq(0)
1
sage: fq(3)
(q^6 - q^5 - q^4 + q^2 + q - 1)/q^6
sage.combinat.similarity_class_type.order_of_general_linear_group(n, q=None)

Return the cardinality of the group of n   imes n invertible matrices with entries in a field of order q.

INPUT:

  • n – a non-negative integer
  • q – an integer or an indeterminate

EXAMPLES:

sage: from sage.combinat.similarity_class_type import order_of_general_linear_group
sage: order_of_general_linear_group(0)
1
sage: order_of_general_linear_group(2)
q^4 - q^3 - q^2 + q
sage.combinat.similarity_class_type.primitives(n, invertible=False, q=None)

Return the number of similarity classes of simple matrices of order n with entries in a finite field of order q. This is the same as the number of irreducible polynomials of degree d.

If invertible is True, then only the number of similarity classes of invertible matrices is returned.

Note

All primitive classes are invertible unless n is 1.

INPUT:

  • n – a positive integer
  • invertible – boolean; if set, only number of non-zero classes is returned
  • q – an integer or an indeterminate

OUTPUT:

  • a rational function of the variable q

EXAMPLES:

sage: from sage.combinat.similarity_class_type import primitives
sage: primitives(1)
q
sage: primitives(1, invertible = True)
q - 1
sage: primitives(4)
1/4*q^4 - 1/4*q^2
sage: primitives(4, invertible = True)
1/4*q^4 - 1/4*q^2

Previous topic

Binary trees

Next topic

Skew Partitions

This Page