4
$\begingroup$

Can we find $n^2$ full-rank matrices in $\mathbb{F}^{n \times n}$ which are linearly independent (i.e. when vectorized are linearly independent)? If not, how many such matrices can be found?

$\endgroup$
1
  • 2
    $\begingroup$ Yes--the set of full-rank matrices is Zariski-open (and non-empty) in $\mathbb{F}^{n\times n}$, so if $k$ is less than $n^2$, the set of full-rank matrices not in the span of $k$ chosen matrices is also Zariski-open and non-empty. (Strictly speaking, this argument only works over finite fields, but it can easily be fixed). This question is more appropriate for math.stackexchange.com. $\endgroup$ Feb 1, 2013 at 5:18

1 Answer 1

4
$\begingroup$

If the characteristic of $\mathbb{F}$ is not two and $E_{i,j}$ $(1\le i,j\le n)$ is the "standard basis", then the matrices $I+E_{i,j}$ are invertible. They are linearly independent if $n+1\ne0$ in $\mathbb{F}$. If the characteristic of $\mathbb{F}$ is greater than 2, we can use $I-E_{i,j}$ instead and these are linearly independent if $n-1\ne0$. So we have explicit examples except in characteristic two.

$\endgroup$
3
  • $\begingroup$ If n > 1, any order n matrix is the sum of exactly two invertible matrices, even if the field has characteristic two. So I would expect an invertible basis for characteristic 2 also. Gerhard "Ask Me About Binary Matrices" Paseman, 2013.02.01 $\endgroup$ Feb 1, 2013 at 23:06
  • $\begingroup$ I agree that there should be an invertible basis in characteristic 2. (Exercise for the reader?) $\endgroup$ Feb 1, 2013 at 23:38
  • $\begingroup$ Consider the cycle q=(1 2 3 ...n) on the set of columns of an order n matrix over F_2 with n > 1. Let Q=q applied to the order n identity matrix, so the main diagonal is shifted "out of the way". In addition to the n(n-1) matrices I + E_ij for i distinct from j, take also the n matrices Q + E_ii. I think this or a slight modification to resolve parity issues should work as a basis in characteristic 2. Gerhard "Ask Me About System Design" Paseman, 2013.02.03 $\endgroup$ Feb 4, 2013 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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