Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  Daniel Litt Feb 1 '13 at 5:18
add comment

1 Answer

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.

share|improve this answer
    
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 –  Gerhard Paseman Feb 1 '13 at 23:06
    
I agree that there should be an invertible basis in characteristic 2. (Exercise for the reader?) –  Chris Godsil Feb 1 '13 at 23:38
    
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 –  Gerhard Paseman Feb 4 '13 at 6:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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