# Polynomials and matrices in $\Bbb F_q$

1. Given a polynomial $p(x,y)\in\Bbb F_q[x,y]$ of $(x,y)$ degree $(n_x,n_y)$ ($n_x,n_y\geq0$ and $n_x,n_y\in\Bbb Z$) where $q=p^\alpha$ with $p$ a prime and $\alpha\in\Bbb N$ how many different matrices $A_1,\dots,A_{k_x}\in \Bbb F_q^{m\times m}$ and $B_1,\dots,B_{k_y}\in \Bbb F_q^{m\times m}$ can we have such that $$p(A_i,B_j)=0$$$$[A_i,B_j]=0$$ holds at every $i\in\{1,\dots,k_x\}$ and every $j\in\{1,\dots,k_y\}$ on the condition $$\operatorname{vec}(A_1),\dots,\operatorname{vec}(A_k)\in\Bbb F_q^{m^2}$$ $$\operatorname{vec}(B_1),\dots,\operatorname{vec}(B_k)\in\Bbb F_q^{m^2}$$ are independent in $\Bbb F_q^{m^2}$?

2. When does $$\mathsf{span}(\operatorname{vec}(A_1,A_2,\dots,A_{k_x}))\cap\mathsf{span}(\operatorname{vec}(B_1,B_2,\dots,B_{k_y}))=\{\underbrace{(0,0,\dots,0)}_{m^2}\}$$ hold?

3. Can we obtain basis for $\mathsf{span}(\operatorname{vec}(A_1,A_2,\dots,A_{k_x}))$ and $\mathsf{span}(\operatorname{vec}(B_1,B_2,\dots,B_{k_y}))$ from coefficients of $p(x,y)$?

There are several reasons this question arose. One of them is coding theory

• Why the vec? It is unnecessary to flatten matrices in your question. – Johannes Hahn Jun 8 '17 at 17:08
• @JohannesHahn then the query may arise what it means for two matrices to be independent and I think it would be better to vec them – Brout Jun 8 '17 at 17:10
• That question doesn't arise as "linear (in)dependence", "span" and all other vector space concepts are defined for every vector space, including the space of matrices. – Johannes Hahn Jun 8 '17 at 17:11
• Also: It's probably best to explicitly add the condition $[A_i,B_j]=0$ in order for $p(A,B)$ to make sense. – Johannes Hahn Jun 8 '17 at 17:25
• And on top of that: Question 3 is simply the question of finding the $A_i$ and $B_j$ themselves because if $A_1,...,A_k$ are linearly independent, then they already are a basis of their span. – Johannes Hahn Jun 8 '17 at 17:52

Consider for a moment the analogue question with a single, fixed $B$, i.e. the question

Question 4: Given $p\in\mathbb{F}_q[X,Y]$ and $B\in\mathbb{F}_q^{m\times m}$, how many linearly independent solutions $A_1, A_2,...\in\mathbb{F}_q^{m\times m}$ to $$[A_i,B]=0, \quad p(A_i,B)=0 \tag{1}$$ can one have?

I claim that this question can be reduced in the generic case to the question

Question 5: Given $d\mid m$ and $\tilde{p}\in\mathbb{F}_{q^d}[X]$, how many $\mathbb{F}_q$-linearly independent solutions $A\in\mathbb{F}_{q^d}^{\frac{m}{d}\times\frac{m}{d}}$ of $\tilde{p}(A)=0$ can one have?

The generic answer to Q4 then depends on the solution to Q5 and on the rational normal form of $B$ (i.e. it is a function of all the $f$ and $\dim\ker(f^k(B))$ with $f\mid\chi_B$ and $k\in\mathbb{N}$).

First observation: If $B$ satisfies a polynomial identity $f(B)=0$ with $f=f_1 \cdot f_2$ and $gcd(f_1,f_2)=1$, then there is a natural decomposition $$V=\underbrace{\ker(f_1(B))}_{:=V'}\oplus\underbrace{\ker(f_2(B))}_{:=V''}$$ into $B$-invariant subspaces and each $A$ commuting with $B$ stabilises both $V'$ and $V''$. If you like to think in terms of matrices and you choose the right basis this means that $B$ is a block diagonal matrix and every solution of $[A,B]=0$ has to be block diagonal as well.

Moreover: Every solution $A_{i_1}'$ of (1) for $B':=B_{|V'}$ can be combined with every solution $A_{i_2}''$ of (1) for $B'':=B_{|V''}$ to the solution $A_{i_1}'\oplus A_{i_2}'':=\begin{pmatrix}A_{i_1}'&\\&A_{i_2}''\end{pmatrix}$ of (1) for $B$. And linear dependence is conserved by this.

Consequence: Answer to Q4 is a product over all irreducible factors of $\chi_B$.

Therefore we have to look at the case where the minimal polynomial of $B$ is of the form $f^k$ with $f$ irreducible and $k\in\mathbb{N}_{>0}$. Let's call the degree of $f$ by the name of $d$. Observe that the characteric polynomial $\chi_B$ must be a power of $f$ so that $d\mid m$ must hold!

In this situation we don't have a natural decomposition into $B$-invariant subspaces any more, but we have a natural flag of $B$-invariant subspaces $$V = \ker(f^k(B)) \supsetneq \ker(f^{k-1}(B)) \supsetneq \ldots \ker(f(B)) \supsetneq 0$$ and every $A$ with $[A,B]=0$ has to stabilise this flag. In terms of matrices w.r.t. a suitable basis: $B$ and $A$ both have a block triagonal form.

As a base for induction consider $k=1$. Then we can choose a decomposition of $V$ into irreducible $B$-invariant, cyclic subspaces. This decomposition is not canonical, so it is not necessarily stabilised, but instead permuted by any $A$ with $[A,B]=0$. In terms of matrices: $B$ can be thought of as $diag(B',B',\ldots,B')$ with $B'\in\mathbb{F}_q^{d\times d}$ the companion matrix of the irreducible polynomial $f$ and $A$ is a $\frac{m}{d}\times\frac{m}{d}$-block matrix whose blocks individually commute with $B'$ (and must therefore be polynomials in $B'$!)

Now consider this decomposition as a $\frac{m}{d}$-dimensional vector space over $\mathbb{F}_{q^d}=\mathbb{F}_q[Y]/f(Y)$. Then $B$ acts as a diagonal matrix and every $A$ with $[A,B]=0$ acts as a $\mathbb{F}_{q^d}^{\frac{m}{d} \times \frac{m}{d}}$-matrix.

The number of linearly independent $A\in\mathbb{F}_q^{m\times m}$ with $[A,B]=0$ and $p(A,B)=0$ is therefore equal to the number of $\mathbb{F}_q$-linearly independent $A\in\mathbb{F}_{q^d}^{\frac{m}{d}\times \frac{m}{d}}$ that satisfy $p(A,\lambda)=0$ where $\lambda\in\mathbb{F}_{q^d}$ is any eigenvalue of $B$. (this number is not dependent on the choice of $\lambda$)

Consequence: For generic $B$ (i.e. diagonalisable over $\overline{\mathbb{F}_q}$ with distinct eigenvalues, i.e. the minimal polynomial of $B$ is square-free) we can answer Q4 by answering Q5 for $\tilde{p}(X) := p(X,\lambda)$ with $\lambda\in spec(B)$.

Take note of a special case: If $d=m$, i.e. $B$ operates irreducible and the block structure consists of a single large block, then we are left with counting $\mathbb{F}_q$-linearly independent zeros of $p(X,\lambda)$ within $\mathbb{F}_{q^m}$ where $\lambda$ is any eigenvalue of $B$ and since $\mathbb{F}_{q^m} = \mathbb{F}_{q^d} = \mathbb{F}_q[\lambda]$ each of these zeros is of the form $g(\lambda)$ for some polynomial $g\in\mathbb{F}_q[X]$.

This can be used to tackle another special case of Q4: If $B$ is a single "rational Jordan-block", i.e. $\dim(\ker(f^j(B)) = \dim(\ker(f^{j-1}(B))+d$ for $1\leq j\leq \frac{m}{d}$, i.e. $\chi_B$ is equal to the minimal polynomial of $B$. Then every $A$ with $[A,B]=0$ is a polynomial of $B$ and vice versa so that we are left with counting solutions $g\in\mathbb{F}_q[X]$ of $p(g(B),B)=0$ such that $g_1(B), g_2(B), ...$ are linearly independent.

This translates to the question:

Question 6: Given $p\in\mathbb{F}_q[X,Y]$, $k\in\mathbb{N}_{>0}$ and an irreducible $f\in\mathbb{F}_q[Y]$, how many $\mathbb{F}_q$-linearly independent solutions $g_1, g_2, \ldots, \in \mathbb{F}_q[Y]/(f(Y)^k)$ of $p(g_i(Y),Y)\equiv 0 \mod f(Y)^k$ are there?

We have already "found" an answer for $k=1$ (because it is really only Q5 for $d=m$). If $gcd(\frac{\partial p}{\partial X},p)\not\equiv 0 \mod f(Y)$, then one can apply Hensel's lemma to the complete local ring $\mathbb{F}_q[Y]/f(Y)^k$ in order to show that every solution for $k=1$ lifts to a unique solution for arbitrary $k$. Linear dependence is conserved as one can readily verify.

Consequence: For generic $p$ and rational Jordan-blocks $B$ we can reduce Q4 to Q5.

Consequence: For generic $p$ and $B$ for which $\chi_B$ is already the minimal polynomial of $B$ we can reduce Q4 to Q5.

At this point I'm out of ideas for now, but I hope you can take something away from my answer.

• I am a little confused about 'to a unique solution for arbitrary k' since k is bounded by a function of q,n,m right? – Brout Jun 8 '17 at 22:53
• Q6 is no longer a statement about matrices, only about polynomials and as such makes sense for all $k$ and the answer is independent of $m$ (and if an $n$ exists anywhere in my post, it's a typo). – Johannes Hahn Jun 8 '17 at 23:00