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 , the
number of similarity class types of
matrices is independent of
.
This makes it possible to perform many combinatorial calculations treating
as a formal variable.
In order to define similarity class types, recall that similarity classes of
matrices with entries in
correspond to functions
such that
where we denote the set of irreducible monic polynomials in
by
, the set of all partitions by
, and
the size of
by
.
Similarity classes indexed by functions and
as above are said to be
of the same type if there exists a degree-preserving self-bijection
of
such that
. Thus, the type
of
remembers only the degrees of the polynomials (and not the polynomials
themselves) for which
takes a certain value
. Replacing each
irreducible polynomial of degree
for which
takes a non-trivial value
by the pair
, we obtain a multiset of such pairs.
Clearly,
and
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
.
For 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 in a given similarity class type, it is possible to calculate
the number elements in the similarity class of
, the dimension of the algebra
of matrices in
that commite with
, and the cardinality of the
subgroup of
that commute with
. 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
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 matrix has rational canonical form type
for
some partition
of
if the diagonal blocks in the rational canonical
form have sizes given by the parts of
. Thus the matrices with rational
canonical type
are the regular ones, while the matrices with rational
canonical type
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 -tuples of
matrices with entries in
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]).
Along with the results of [PSS13], similarity class types can be used to
calculate the number of similarity classes of matrices of order with entries
in a principal ideal local ring of length two with residue field of cardinality
with centralizer of any given cardinality up to
. Among these, the
classes which are selftranspose can also be counted:
sage: from sage.combinat.similarity_class_type import matrix_centralizer_cardinalities_length_two
sage: list(matrix_centralizer_cardinalities_length_two(3))
[(q^6 - 3*q^5 + 3*q^4 - q^3, 1/6*q^6 - 1/2*q^5 + 1/3*q^4),
(q^6 - 2*q^5 + q^4, q^5 - q^4),
(q^8 - 3*q^7 + 3*q^6 - q^5, 1/2*q^5 - q^4 + 1/2*q^3),
(q^8 - 2*q^7 + q^6, q^4 - q^3),
(q^10 - 2*q^9 + 2*q^7 - q^6, q^4 - q^3),
(q^8 - q^7 - q^6 + q^5, 1/2*q^5 - q^4 + 1/2*q^3),
(q^6 - q^5 - q^4 + q^3, 1/2*q^6 - 1/2*q^5),
(q^6 - q^5, q^4),
(q^10 - 2*q^9 + q^8, q^3),
(q^8 - 2*q^7 + q^6, q^4 - q^3),
(q^8 - q^7, q^3 + q^2),
(q^12 - 3*q^11 + 3*q^10 - q^9, 1/6*q^4 - 1/2*q^3 + 1/3*q^2),
(q^12 - 2*q^11 + q^10, q^3 - q^2),
(q^14 - 2*q^13 + 2*q^11 - q^10, q^3 - q^2),
(q^12 - q^11 - q^10 + q^9, 1/2*q^4 - 1/2*q^3),
(q^12 - q^11, q^2),
(q^14 - 2*q^13 + q^12, q^2),
(q^18 - q^17 - q^16 + q^14 + q^13 - q^12, q^2),
(q^12 - q^9, 1/3*q^4 - 1/3*q^2),
(q^6 - q^3, 1/3*q^6 - 1/3*q^4)]
REFERENCES:
[Green55] | Green, J. A. The characters of the finite general linear groups. Trans. Amer. Math. Soc. 80 (1955), 402–447. doi: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. https://cs.uwaterloo.ca/journals/JIS/VOL9/Morrison/morrison37.html |
[PSS13] | (1, 2) Prasad, A., Singla, P., and Spallone, S., Similarity of matrices over local rings of length two. Arxiv 1212.6157 |
AUTHOR:
- Amritanshu Prasad (2013-07-18): initial implementation
- Amritanshu Prasad (2013-09-09): added functions for similarity classes over rings of length two
-
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
and a positive integer
, the primary similarity class type
represents similarity classes of square matrices of order
with entries in a finite field of order
which correspond to the
-module
for some irreducible polynomial
of degree
.
-
centralizer_algebra_dim
()¶ Return the dimension of the algebra of matrices which commute with a matrix of type
self
.For a partition
this dimension is given by
.
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 orderq
.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
where
is the value returned by
func
upon input, if
self
is.
EXAMPLES:
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 ofmin
or whose degree is that ofmin
and whose partition is less than ofmin
in lexicographic order.A primary similarity class type of size
is a pair
consisting of a partition
and a positive integer
such that
.
INPUT:
n
– a positive integermin
– a primary matrix type of sizen
EXAMPLES:
If
min
is not specified, then the class of all primary similarity class types of sizen
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 ofmin
or whose degree is that ofmin
and whose partition is less than ofmin
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
is
.
EXAMPLES:
sage: PTC = PrimarySimilarityClassTypes(2) sage: PTC.size() 2
-
class
sage.combinat.similarity_class_type.
SimilarityClassType
(parent, tau)¶ Bases:
sage.combinat.combinat.CombinatorialElement
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 keyis the partition formed by sorting the degrees of primary types with partition
.
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
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 inself
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 inself
has all parts equal to1
.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
.INPUT:
invertible
– Boolean; return number of invertible classes if set toTrue
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
where
is the value returned by
func
on the input.
INPUT:
func
– a function that takes a partition to a polynomial inq
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 typemin
.A similarity class type is a multiset of primary matrix types.
INPUT:
n
– a non-negative integermin
– a primary similarity class type
EXAMPLES:
If
min
is not specified, then the class of all matrix types of sizen
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 ofmin
, or if they have size equal to that ofmin
, then they occur aftermin
in the iterator forPrimarySimilarityClassTypes(n)
, wheren
is the size ofmin
: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
(these could be polynomials or rational functions in
, for each similarity class type
define
This function returns
where
denotes the type of a matrix
, and the sum is over all
matrices if
sumover
is set to"matrices"
, is over allsimilarity classes if
sumover
is set to"classes"
, and over alltypes if
sumover
is set to"types"
. Ifinvertible
is set toTrue
, then the sum is only over invertible matrices or classes.INPUT:
stat
– a function which takes partitions and returns a function ofq
sumover
– can be one of the following:"matrices"
"classes"
"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
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
of a nilpotent matrix whose Jordan blocks are given by
la
.INPUT:
lambda
– a partitionq
– 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.
dictionary_from_generator
(gen)¶ Given a generator for a list of pairs
, construct a dictionary whose keys are the distinct values for
and whose value at
is the sum of
over all pairs of the form
such that
.
EXAMPLES:
sage: from sage.combinat.similarity_class_type import dictionary_from_generator sage: dictionary_from_generator(((floor(x/2), x) for x in xrange(10))) {0: 1, 1: 5, 2: 9, 3: 13, 4: 17}
It also works with lists:
sage: dictionary_from_generator([(floor(x/2),x) for x in range(10)]) {0: 1, 1: 5, 2: 9, 3: 13, 4: 17}
Note
Since the generator is first converted to a list, memory usage could be high.
-
sage.combinat.similarity_class_type.
ext_orbit_centralizers
(input_data, q=None, selftranspose=False)¶ Generate pairs consisting of centralizer cardinalities of orbits in
for the action of
, where
is the
-module constructed from
input
and their frequencies.INPUT:
input_data
– input forinput_parsing()
q
– (default:) an integer or an indeterminate
selftranspose
– (default:False
) boolean stating if we only want selftranspose type
TESTS:
sage: from sage.combinat.similarity_class_type import ext_orbit_centralizers sage: list(ext_orbit_centralizers([6, 1])) [(q^9 - 2*q^8 + q^7, q^6), (q^7 - 2*q^6 + q^5, q^7 - q^6), (q^7 - q^6, q^6 + q^5)] sage: list(ext_orbit_centralizers([6, 1], selftranspose = True)) [(q^9 - 2*q^8 + q^7, q^6), (q^7 - 2*q^6 + q^5, q^7 - q^6), (q^7 - q^6, q^6 - q^5)] sage: list(ext_orbit_centralizers([6, 1, 1])) [(q^12 - 3*q^11 + 3*q^10 - q^9, 1/2*q^7 - 1/2*q^6), (q^8 - 3*q^7 + 3*q^6 - q^5, 1/2*q^8 - q^7 + 1/2*q^6), (q^12 - 2*q^11 + q^10, q^6), (q^8 - 2*q^7 + q^6, q^7 - q^6), (q^14 - 2*q^13 + 2*q^11 - q^10, q^6), (q^10 - 2*q^9 + 2*q^7 - q^6, q^7 - q^6), (q^12 - q^11 - q^10 + q^9, 1/2*q^7 - 1/2*q^6), (q^8 - q^7 - q^6 + q^5, 1/2*q^8 - q^7 + 1/2*q^6), (q^8 - 2*q^7 + q^6, q^7 - q^6), (q^8 - q^7, q^6 + 2*q^5), (q^10 - 2*q^9 + q^8, 2*q^6)] sage: list(ext_orbit_centralizers([6, 1, 1], selftranspose = True)) [(q^12 - 3*q^11 + 3*q^10 - q^9, 1/2*q^7 - 1/2*q^6), (q^8 - 3*q^7 + 3*q^6 - q^5, 1/2*q^8 - q^7 + 1/2*q^6), (q^12 - 2*q^11 + q^10, q^6), (q^8 - 2*q^7 + q^6, q^7 - q^6), (q^14 - 2*q^13 + 2*q^11 - q^10, q^6), (q^10 - 2*q^9 + 2*q^7 - q^6, q^7 - q^6), (q^12 - q^11 - q^10 + q^9, 1/2*q^7 - 1/2*q^6), (q^8 - q^7 - q^6 + q^5, 1/2*q^8 - q^7 + 1/2*q^6), (q^8 - 2*q^7 + q^6, q^7 - q^6), (q^8 - q^7, q^6)] sage: list(ext_orbit_centralizers([2, [6, 1, 1]], selftranspose = True)) [(q^24 - 3*q^22 + 3*q^20 - q^18, 1/2*q^14 - 1/2*q^12), (q^16 - 3*q^14 + 3*q^12 - q^10, 1/2*q^16 - q^14 + 1/2*q^12), (q^24 - 2*q^22 + q^20, q^12), (q^16 - 2*q^14 + q^12, q^14 - q^12), (q^28 - 2*q^26 + 2*q^22 - q^20, q^12), (q^20 - 2*q^18 + 2*q^14 - q^12, q^14 - q^12), (q^24 - q^22 - q^20 + q^18, 1/2*q^14 - 1/2*q^12), (q^16 - q^14 - q^12 + q^10, 1/2*q^16 - q^14 + 1/2*q^12), (q^16 - 2*q^14 + q^12, q^14 - q^12), (q^16 - q^14, q^12)] sage: list(ext_orbit_centralizers([[2, [6, 1, 1]]], selftranspose = True)) [(q^24 - 3*q^22 + 3*q^20 - q^18, 1/2*q^14 - 1/2*q^12), (q^16 - 3*q^14 + 3*q^12 - q^10, 1/2*q^16 - q^14 + 1/2*q^12), (q^24 - 2*q^22 + q^20, q^12), (q^16 - 2*q^14 + q^12, q^14 - q^12), (q^28 - 2*q^26 + 2*q^22 - q^20, q^12), (q^20 - 2*q^18 + 2*q^14 - q^12, q^14 - q^12), (q^24 - q^22 - q^20 + q^18, 1/2*q^14 - 1/2*q^12), (q^16 - q^14 - q^12 + q^10, 1/2*q^16 - q^14 + 1/2*q^12), (q^16 - 2*q^14 + q^12, q^14 - q^12), (q^16 - q^14, q^12)]
-
sage.combinat.similarity_class_type.
ext_orbits
(input_data, q=None, selftranspose=False)¶ Return the number of orbits in
for the action of
, where
is the
-module constructed from
input_data
.INPUT:
input_data
– input forinput_parsing()
q
– (default:) an integer or an indeterminate
selftranspose
– (default:False
) boolean stating if we only want selftranspose type
TESTS:
sage: from sage.combinat.similarity_class_type import ext_orbits sage: ext_orbits([6, 1]) q^7 + q^6 + q^5 sage: ext_orbits([6, 1], selftranspose = True) q^7 + q^6 - q^5 sage: ext_orbits([6, 1, 1]) q^8 + 2*q^7 + 2*q^6 + 2*q^5 sage: ext_orbits ([6, 1, 1], selftranspose = True) q^8 + 2*q^7 sage: ext_orbits([2, 2]) q^4 + q^3 + q^2 sage: ext_orbits([2, 2], selftranspose = True) q^4 + q^3 + q^2 sage: ext_orbits([2, 2, 2]) q^6 + q^5 + 2*q^4 + q^3 + 2*q^2 sage: ext_orbits([2, 2, 2], selftranspose = True) q^6 + q^5 + 2*q^4 + q^3 sage: ext_orbits([2, 2, 2, 2]) q^8 + q^7 + 3*q^6 + 3*q^5 + 5*q^4 + 3*q^3 + 3*q^2 sage: ext_orbits([2, 2, 2, 2], selftranspose = True) q^8 + q^7 + 3*q^6 + 3*q^5 + 3*q^4 + q^3 + q^2 sage: ext_orbits([2, [6, 1]]) q^14 + q^12 + q^10 sage: ext_orbits([[2, [6, 1]]]) q^14 + q^12 + q^10
-
sage.combinat.similarity_class_type.
fq
(n, q=None)¶ Return
.
INPUT:
n
– A non-negative integerq
– 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.
input_parsing
(data)¶ Recognize and return the intended type of
input
.TESTS:
sage: from sage.combinat.similarity_class_type import input_parsing sage: input_parsing(Partition([2, 1])) ('par', [2, 1]) sage: input_parsing(PrimarySimilarityClassType(2, [2, 1])) ('pri', [2, [2, 1]]) sage: input_parsing(SimilarityClassType([[2, [2, 1]]])) ('sim', [[2, [2, 1]]]) sage: input_parsing([2, 1]) ('par', [2, 1]) sage: input_parsing([2, [2, 1]]) ('pri', [2, [2, 1]]) sage: input_parsing([[2, [2, 1]]]) ('sim', [[2, [2, 1]]])
-
sage.combinat.similarity_class_type.
matrix_centralizer_cardinalities
(n, q=None, invertible=False)¶ Generate pairs consisting of centralizer cardinalities of matrices over a finite field and their frequencies.
TESTS:
sage: from sage.combinat.similarity_class_type import matrix_centralizer_cardinalities sage: list(matrix_centralizer_cardinalities(1)) [(q - 1, q)] sage: list(matrix_centralizer_cardinalities(2)) [(q^2 - 2*q + 1, 1/2*q^2 - 1/2*q), (q^2 - q, q), (q^4 - q^3 - q^2 + q, q), (q^2 - 1, 1/2*q^2 - 1/2*q)] sage: list(matrix_centralizer_cardinalities(2, invertible = True)) [(q^2 - 2*q + 1, 1/2*q^2 - 3/2*q + 1), (q^2 - q, q - 1), (q^4 - q^3 - q^2 + q, q - 1), (q^2 - 1, 1/2*q^2 - 1/2*q)]
-
sage.combinat.similarity_class_type.
matrix_centralizer_cardinalities_length_two
(n, q=None, selftranspose=False, invertible=False)¶ Generate pairs consisting of centralizer cardinalities of matrices over a principal ideal local ring of length two with residue field of order
q
and their frequencies.INPUT:
n
– the orderq
– (default:) an integer or an indeterminate
selftranspose
– (default:False
) boolean stating if we only want selftranspose typeinvertible
– (default:False
) boolean stating if we only want invertible type
TESTS:
sage: from sage.combinat.similarity_class_type import matrix_centralizer_cardinalities_length_two sage: list(matrix_centralizer_cardinalities_length_two(1)) [(q^2 - q, q^2)] sage: list(matrix_centralizer_cardinalities_length_two(2)) [(q^4 - 2*q^3 + q^2, 1/2*q^4 - 1/2*q^3), (q^4 - q^3, q^3), (q^6 - 2*q^5 + q^4, 1/2*q^3 - 1/2*q^2), (q^6 - q^5, q^2), (q^8 - q^7 - q^6 + q^5, q^2), (q^6 - q^4, 1/2*q^3 - 1/2*q^2), (q^4 - q^2, 1/2*q^4 - 1/2*q^3)] sage: from sage.combinat.similarity_class_type import dictionary_from_generator sage: dictionary_from_generator(matrix_centralizer_cardinalities_length_two(2, q = 2)) {4: 4, 8: 8, 12: 4, 16: 2, 32: 4, 48: 2, 96: 4}
-
sage.combinat.similarity_class_type.
matrix_similarity_classes
(n, q=None, invertible=False)¶ Return the number of matrix similarity classes over a finite field of order
q
.TESTS:
sage: from sage.combinat.similarity_class_type import matrix_similarity_classes sage: matrix_similarity_classes(2) q^2 + q sage: matrix_similarity_classes(2, invertible = True) q^2 - 1 sage: matrix_similarity_classes(2, invertible = True, q = 4) 15
-
sage.combinat.similarity_class_type.
matrix_similarity_classes_length_two
(n, q=None, selftranspose=False, invertible=False)¶ Return the number of similarity classes of matrices of order
n
with entries in a principal ideal local ring of length two.INPUT:
n
– the orderq
– (default:) an integer or an indeterminate
selftranspose
– (default:False
) boolean stating if we only want selftranspose typeinvertible
– (default:False
) boolean stating if we only want invertible type
EXAMPLES:
We can generate Table 6 of [PSS13]:
sage: from sage.combinat.similarity_class_type import matrix_similarity_classes_length_two sage: matrix_similarity_classes_length_two(2) q^4 + q^3 + q^2 sage: matrix_similarity_classes_length_two(2, invertible = True) q^4 - q sage: matrix_similarity_classes_length_two(3) q^6 + q^5 + 2*q^4 + q^3 + 2*q^2 sage: matrix_similarity_classes_length_two(3, invertible = true) q^6 - q^3 + 2*q^2 - 2*q sage: matrix_similarity_classes_length_two(4) q^8 + q^7 + 3*q^6 + 3*q^5 + 5*q^4 + 3*q^3 + 3*q^2 sage: matrix_similarity_classes_length_two(4, invertible = True) q^8 + q^6 - q^5 + 2*q^4 - 2*q^3 + 2*q^2 - 3*q
And also Table 7:
sage: matrix_similarity_classes_length_two(2, selftranspose = True) q^4 + q^3 + q^2 sage: matrix_similarity_classes_length_two(2, selftranspose = True, invertible = True) q^4 - q sage: matrix_similarity_classes_length_two(3, selftranspose = True) q^6 + q^5 + 2*q^4 + q^3 sage: matrix_similarity_classes_length_two(3, selftranspose = True, invertible = True) q^6 - q^3 sage: matrix_similarity_classes_length_two(4, selftranspose = True) q^8 + q^7 + 3*q^6 + 3*q^5 + 3*q^4 + q^3 + q^2 sage: matrix_similarity_classes_length_two(4, selftranspose = True, invertible = True) q^8 + q^6 - q^5 - q
-
sage.combinat.similarity_class_type.
order_of_general_linear_group
(n, q=None)¶ Return the cardinality of the group of
invertible matrices with entries in a field of order
q
.INPUT:
n
– a non-negative integerq
– 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 orderq
. This is the same as the number of irreducible polynomials of degree.
If
invertible
isTrue
, then only the number of similarity classes of invertible matrices is returned.Note
All primitive classes are invertible unless
n
is.
INPUT:
n
– a positive integerinvertible
– boolean; if set, only number of non-zero classes is returnedq
– 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