3
$\begingroup$

Let $ f$ be an irreducible polynomial of degree $q$ over $\mathbb{F}_p$. Let ${\bf F}=\frac{\mathbb{F}_p[x]}{f}$ be the finite field which contain $p^q$ elements. Assume $k>1$ is an integer and suppose that ${\bf R}=\frac{\mathbb{F}_p[x]}{f^k}$ is the quotient ring such that the coefficients come from $\mathbb{F}_p$ and the multiplication of elements are reduced by $f^k$.

Let $\bf A$ be an $n \times m$ matrix such that the elements of $\bf A$ are polynomials over $\mathbb{F}_p[x]$. Suppose that the minimum number of linearly dependent columns of the matrix $\bf A$ over ${\bf F}$ and ${\bf R}$ are denoted with ${\operatorname{MD}}_F$ and ${\operatorname{MD}}_R$, respectively.

My question:

How to prove that if ${\operatorname{MD}}_F=r$ for some positive integer $1\leq r \leq m$, then ${\operatorname{MD}}_R \geq r$.

Furthermore, Is it possible to make some conditions over $\bf A$ such that we have ${\operatorname{MD}}_F=r$ and ${\operatorname{MD}}_R > r$.

In practical, I work with $p=2$.

Thanks for any help.

$\endgroup$
  • $\begingroup$ Is the minimum number of linearly dependent columns the minimum number $k$ such that there exists a subset $k$ of the columns which are linearly dependent? In the $R$ case, do you require at least one of the coefficients of the linear relation to be a unit? $\endgroup$ – Will Sawin Jun 30 at 17:57
  • $\begingroup$ @WillSawin You wrote correctly (the minimum number of linearly dependent columns the minimum number k such that there exists a subset k of the columns which are linearly dependent). About your second question, the question does not require that at least one of the coefficients of the linear relation to be a unit. In fact, I would like to solve the question in the case $p=2$ and I want to ask you to consider this case. Thanks for your comment. $\endgroup$ – user0410 Jun 30 at 18:08
5
$\begingroup$

We in fact have $MD_R = MD_F$.

Given a linear relation over $F$, to form the corresponding linear relation over $R$, simply multiply each coefficient with $f^{k-1}$, which is well defined because $F = \mathbb F_q[T]/f$ and $R = \mathbb F_q[T]/f^k$. For the same reason, because the linear relation over $F$ holds mod $f$, multiplying each coefficient by $f^{k-1}$ produces a linear relation that holds mod $f^k$. Furthermore all the nonzero coefficients remain nonzero when we do this, so this is a nontrivial relation.

Given a linear relation over $R$, to form the corresponding linear relation over $F$, find the minimum $j$ such that $f^j$ divides each coefficient. We may lift the coefficients from $\mathbb F_q[T]/f^k$ to $\mathbb F_q[T]$, then divide by $f^j$, and finally mod out by $f$. The relations will still hold because they hold mod $f^k$ and $k>j$ because the coefficients aren’t all zero.

Each of these processes preserves or reduces the number of variables appearing the in the relation, and keeps it nontrivial, so the minimum number of variables is the same over $R$ and $F$.

$\endgroup$
  • $\begingroup$ I thank you for your careful and excellent revisions. I got it. $\endgroup$ – user0410 Jun 30 at 22:24

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.