Matrices modulo \(p^k\) and \(k\) commuting matrices modulo \(p\)
1 Similarity and simultaneous similarity
1.1 Definition of Similarity
Matrices \(A\) and \(B\) in \(M_n(R)\) are similar if there exists \(X\in GL_n(R)\) such that \[ XAX^{-1} = B. \]
Here \(R\) can be any ring.
1.2 Simultaneous Similarity
The tuple \((A_1, \dotsc, A_k)\) is similar to the tuple \((B_1,\dotsc, B_k)\) if there exists \(X\in GL_n(R)\) such that \[ XA_1X^{-1} = B_1, XA_2X^{-1} = B_2, \cdots, XA_kX^{-1} = B_k. \]
2 Classes in a Field
2.1 Rational Canonical Form
\[ A \sim C_{f_1}\oplus C_{f_2} \oplus \dotsb \oplus C_{f_k} \]
where \(f_k|f_{k-1}|\dotsc|f_1\).
Here \(C_f\) is the companion matrix of \(f\).
2.2 In a finite field
Let \(\lambda = (\lambda_1,\dotsc, \lambda_k)\) be a partition of \(n\).
Number of classes with \(\deg(f_i) = \lambda_i\) is \[ q^{\lambda_k + (\lambda_{k-1} - \lambda_k) + \dotsb (\lambda_2 - \lambda_1)} = q^{\lambda_1} \]
Why?
\(f_1,\dotsc, f_k\) is determined by \(f_1/f_2, f_2/f_3,\dotsc, f_{k-1}/f_k, f_k\).
No. of choices for \(f_i/f_{i+1} = q^{\lambda_i - \lambda_{i+1}}\).
3 Matrix tuple problem
\[ a_{n,k}(q) = \begin{array}{l}\text{No. of simultaneous similarity classes of}\\ \text{\(k\)-tuples of \(n\times n\) matrices over $\mathbf F_q$}.\end{array} \]
3.1 Burnside's Lemma:
\[ a_{n,k}(q) = \frac 1{|GL_n(\mathbf F_q)|}\sum_{g\in GL_n(\mathbf F_q)} |Z_{M_n(\mathbf F_q)}(g)|^k. \]
Shows that
\[ A_n(q, t) = \sum_{k=0}^\infty a_{n,k}(q)t^k = \frac 1{|GL_n(\mathbf F_q)|}\sum_{g\in GL_n(\mathbf F_q)} \frac 1{1-|Z_{M_n(\mathbf F_q)}(g)|t}, \]
is a rational function of \(t\) for each \(n\).
4 Theory of Types
4.1 Jordan normal form
Similarity classes in \(M_n(\mathbf F_q)\) correspond to \[ \{\phi : \mathrm{Irr}\mathbf F_q[t] \to \Lambda\mid \sum_{f\in\mathrm{Irr}\mathbf F_q[t]} \deg(f)|\phi(f)| = n\} \]
4.2 Types
Classes \(\phi_1\) and \(\phi_2\) have the same type if
\[ \phi_2 = \phi_2\circ \sigma \]
for some degree-preserving bijection \(\sigma: \mathrm{Irr}\mathbf F_q[t]\to \mathrm{Irr}\mathbf F_q[t]\).
5 Why types are useful
5.1 Types are combinatorial
- Given \(\phi\), define \(\tau:\Lambda\to \Lambda\) by \[ \tau_\phi(\lambda) = (1^{m_1}, 2^{m_2}, \dotsc) \] where \(m_i\) is the number of irreducible polynomials \(f\) of degree \(i\) such that \(\phi(i) = \lambda\). Then \(\phi_1\) and \(\phi_2\) have the same type if and only if \(\tau_{\phi_1} = \tau_{\phi_2}\).
- The set of types is a combinatorial object; types correspond to functions \[ \{\tau: \Lambda\to \Lambda \mid \sum_{\lambda\in \Lambda} |\lambda||\tau(\lambda)| = n\} \]
- The number of matrices of each type can be counted
- Matrices of the same type have isomorphic centralizers
6 Computer Implementation
sage: from sage.combinat.similarity_class_type import * 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
7 Kac conjecture
- Usually stated in the framework of quivers
- When the quiver has one vertex and \(k\) loops (bouquet quiver) isomorphism classes of representations are simultaneous similarity classes of matrices
7.1 Conjecture (V. Kac, 1983)
\(a_{n,k}(q)\) is a polynomial in \(q\) with non-negative integer coefficients
This result was proved by Hausel, Letellier and Rodriguez-Villegas, 2013.
8 Commuting Matrix Tuple Problem
\[ b_{n,k}(q) = \begin{array}{l}\text{No. of simultaneous similarity classes of}\\ \text{\(k\)-tuples of commuting \(n\times n\) matrices over $\mathbf F_q$}.\end{array} \]
8.1 Generating function
\[ B_n(q, t) = \sum_{k = 0}^\infty b_{n,k}(q) t^k \]
This is a rational function.
8.2 Not known
Are its coefficients polynomials in \(q\)?
9 Explicit Computation (Uday Bhaskar Sharma)
| \(n\) | \(B_n(q,t)\) |
|---|---|
| 1 | \(\frac{1}{1-qt}\) |
| 2 | \(\frac{1}{(1-qt)(1-q^2t)}\) |
| 3 | \(\frac{1+q^2t^2}{(1-qt)(1-q^2t)(1-q^3t)}\) |
| 4 | \(\left(\frac{1+q^2t+2q^2t^2+q^3t^2+2q^4t^2+q^6t^3}{(1-qt)(1-q^2t)(1-q^3t)(1-q^4t)(1-q^5t)} \right)\) |
| \(- \left(\frac{q^5t+q^7t^2+q^3t^3+2q^7t^3+2q^9t^3+q^{10}t^4}{(1-qt)(1-q^2t)(1-q^3t)(1-q^4t)(1-q^5t)} \right)\) |
9.1 Conclusion
\(b_{n,k}(q)\) is a polynomial in \(q\) with non-negative integer coefficients for \(n\leq 4\).
10 Similarity classes modulo \(p^k\)
\[ c_{n,k}(q) = \text{No. of similarity classes of \(n\times n\) matrices in $M_n(\mathbf Z/p^k \mathbf Z)$}. \]
10.1 Generating Function
\[ C_n(q, t) = \sum_{k=0}^\infty c_{n,k}(q)t^k \]
is known to be a rational function of \(t\).
11 Calculations for \(k = 2\) (Prasad, Singla and Spallone)
| \(n\) | \(c_{n,2}(q)\) |
|---|---|
| \(2\) | \(q^4 + q^3 + q^2\) |
| \(3\) | \(q^6+q^5+2q^4+q^3+2q^2\) |
| \(4\) | \(q^8 + q^7 + 3q^6 + 3q^5 + 5q^4 + 3q^3 + 3q^2\) |
12 Relation to simultaneous similarity classes
12.0.1 two_theorem
\[ b_{n,2}(p) = c_{n,2}(p). \] See Singla, Jambor and Plesken and also: Prasad, Singla and Spallone, Remark 1.1
13 Outline of Proof
13.0.1 Main Lemma Main_Lemma
For every \(A\in M_n(\mathbf Z/p\mathbf Z)\), there exists \(\tilde A in M_n(\mathbf Z/p^2\mathbf Z)\) such that for every \(B\in M_n(\mathbf Z/p\mathbf Z)\) that commutes with \(A\) there exists \(\tilde B in M_n(\mathbf Z/p^2\mathbf Z)\) that commutes with \(\tilde A\).
14 A reduction
Let \(A\in M_n(\mathbf Z/p\mathbf Z)\).
Define \[ G_A = \{\tilde X \in GL_n(\mathbf Z/p^2\mathbf Z)\mid \tilde X\tilde A \cong \tilde A\tilde X \mod p\}. \]
The map: \[ C\mapsto C\cap \tilde A + pM_n(\mathbf Z/p\mathbf Z) \]
defines a bijection from the set of similarity classes in \(M_n(\mathbf Z/p^2\mathbf Z)\) which which contain a lift of \(A\) to the set of \(G_A\)-orbits in \(\tilde A + pM_n(\mathbf Z/p\mathbf Z)\).
So, in order to classify similarity classes in \(M_n(\mathbf Z/p^2\mathbf Z)\), it suffices to
- classify similarity classes in \(M_n(\mathbf Z/p\mathbf Z)\) (which has been done)
- for some \(A\) in each such class, find \(G_A\)-orbits in \(\tilde A + pM_n(\mathbf Z/p\mathbf Z)\)
15 A lemma on group actions
15.1 The lemma
Let \(G\) be a group acting on a set \(X\), and let \(N\) be a normal subgroup of \(G\).
Then \(G/N\) has a well-defined action on \(N\backslash X\), and
\[ G\backslash X = (G/N)\backslash (N\backslash X). \]
15.2 In our case
\(G = G_A\), \(X = \tilde A + pM_n(\mathbf Z/p\mathbf Z)\).
\(N = \{I + pX\mid X\in M_n(\mathbf Z/p\mathbf Z)\).
\(G/N\) is isomorphic to \(Z_{GL_n(\mathbf Z/p\mathbf Z)}A\).
16 \(N\)-orbits in \(X\)
\(\tilde A + p X\) and \(\tilde A + pY\) are in the same \(N\) orbit if and only if there exists \(U\in M_n(\mathbf Z/p\mathbf Z)\) such that
\[ (I + pU)(\tilde A + pX) = (\tilde A + pY)(I + pU). \]
Equivalently
\[ X - Y \in [A, M_n(\mathbf Z/p\mathbf Z)]. \]
So: \[ N\backslash X = M_n(\mathbf Z/p\mathbf Z)/ [A, M_n(\mathbf Z/p\mathbf Z)] \]
17 Duality
Identify \(M_n(\mathbf Z/p\mathbf Z)\) with its linear dual using the non-degenerate bilinear form \[ \langle X, Y\rangle = \mathrm{trace}(XY). \]
This form is invariant under the action of \(GL_n(\mathbf Z/p\mathbf Z)\), and so also the action of \(G/N = Z_{GL_n(\mathbf Z/p\mathbf Z)}(A)\).
This gives rise to an isomorphism
\[ \left( \frac{M_n(\mathbf Z/p\mathbf Z)}{[A, M_n(\mathbf Z/p\mathbf Z)]} \right)^* = Z_{M_n(\mathbf Z/p\mathbf Z)}(A) \]
which preserves the action of \(Z_{GL_n(\mathbf Z/p\mathbf Z)}(A)\).
18 Group actions on vector spaces and their duals
Let \(X\) be a finite vector space, and \(G\) be a finite group acting by linear maps.
Then \[ {}|G\backslash X | = | G\backslash X^*| \]
This follows from Burnside's lemma:
\[ {}|G\backslash X | = \frac 1{|G|} \sum_{g\in G} |X^g| \]
Now note that \(X^g\) is the \(1\)-eigenspace of \(g\), which has the same dimension as the \(1\)-eigenspace of \(g^*\).
19 Finishing the proof
So the number of similarity classes in \(M_n(\mathbf Z/p^2\mathbf Z)\) which contain an element congruent to \(A\mod p\) is
\[ Z_{GL_n(\mathbf Z/p\mathbf Z)}(A) \backslash \Big(M_n(\mathbf Z/p\mathbf Z)/[A, M_n(\mathbf Z/p\mathbf Z)]\Big) \]
which is the same as \[ Z_{GL_n(\mathbf Z/p\mathbf Z)}(A) \backslash Z_{M_n(\mathbf Z/p\mathbf Z)}(A) \]
So the number \(c_{n,k}(p)\) of similarity classes in \(M_n(\mathbf Z/p^\mathbf Z)\) is
\[ \sum_A |Z_{GL_n(\mathbf Z/p\mathbf Z)}(A) \backslash Z_{M_n(\mathbf Z/p\mathbf Z)}(A)| \]
the sum being over all similarity classes in \(M_n(\mathbf Z/p\mathbf Z)\).
This is \(b_{n,k}(p)\).
20 Conjectures
- \(B_n(p, t) = C_n(p, t)\) for all \(n\).
This is known for \(n\leq 3\), by work of Avni, Onn, Prasad and Vaserstein
- these are polynomials in \(p\) with non-negative integer coefficients.