蹦迪是什么意思

Question

Consider the space of $n \times n$ matrices over the finite field $GF(2)$. Is it possible to choose $k$ matrices $A_i, i = 1 ,\cdots k$, such that for every non-zero vector $b \in \{0,1\}^k$ the matrix $\sum_{i=1}^k (b)_i A_i$ (with $(b)_i$ being the $i$-th entry of $b$) is full-rank? What is the largest $k$ for which this is possible? Is this possible for $k=n$?

I found that for $k=n=2$ we can simply take $A_1 = \left[\begin{matrix} 1&0\\ 0&1\end{matrix}\right]$ and $A_2 = \left[\begin{matrix} 1&1\\ 1&0\end{matrix}\right]$. Moreover, it is not hard to show that $k=2$ is the largest $k$ for which this is possible in $\{0,1\}^{2\times 2}$ (there are only 6 full-rank matrices in $\{0,1\}^{2\times 2}$ with the field $GF(2)$, after all). Similar matrices can be used for $k=2$ when $n > 2$, but I haven't found anything else. I feel like like the case $k=n$ should be possible in general, or at the very least $k=\lfloor n/2\rfloor$. but I haven't found valid matrices for $k=3$ and $n > 2$.

Thanks in advance.

Answer 1

For $k\leqslant n$ such $k$ matrices exist. Take an irreducible polynomial $p$ of degree $n$, its companion matrix $A$ (a matrix with characterstic polynomial $p$) and $k$ matrices $A^i$ for $i=0,\dots,k-1$. Put $g(t)=\sum b_i t^i$. Recall that $p(A)=0$ by Hamilton -- Cayley. Since $0<\deg g\leqslant k-1<n$, the polynomials $p, g$ are coprime, thus, there exist the polynomials $f_1,f_2$ for which $f_1(t)p(t)+f_2(t)g(t)\equiv 1$. Then, $f_2(A)g(A)=f_1(A)p(A)+f_2(A)g(A)=I$, so, $g(A)$ is invertible.

But $n+1$ or more matrices do not exist: for every $n+1$ matrices there exist their non-trivial linear combination for which the first column is zero.