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

  • $\begingroup$ Why the vec? It is unnecessary to flatten matrices in your question. $\endgroup$ Jun 8, 2017 at 17:08
  • $\begingroup$ @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 $\endgroup$
    – Turbo
    Jun 8, 2017 at 17:10
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 8, 2017 at 17:11
  • 2
    $\begingroup$ Also: It's probably best to explicitly add the condition $[A_i,B_j]=0$ in order for $p(A,B)$ to make sense. $\endgroup$ Jun 8, 2017 at 17:25
  • $\begingroup$ 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. $\endgroup$ Jun 8, 2017 at 17:52

1 Answer 1


Partial answer:

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.

  • $\begingroup$ 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? $\endgroup$
    – Turbo
    Jun 8, 2017 at 22:53
  • 1
    $\begingroup$ 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). $\endgroup$ Jun 8, 2017 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.