# 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. 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
– Mr.
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. 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. 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. 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?
– Mr.
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). Jun 8 '17 at 23:00