12
$\begingroup$

I have been reading J.S. Milne's lecture notes on fields and Galois theory and came across the normal basis theorem (Thm 5.18 on page 66 of the notes). Trying to find my own proof, the following problem in linear algebra quickly arose:

Question: Let $F$ be a field. Given linearly independent matrices $A_1, \dots, A_n \in \operatorname{GL}_n(F)$, does there necessarily exist some $b\in F^n$ such that $A_1b, \dots, A_nb$ are linearly independent over $F$?

This is clearly not true if the matrices are not linearly independent. Also, if they are not invertible, the claim is false in general: e.g. set $n=2$ and consider

$$A_1 = \begin{pmatrix} 1 & 0 \\ 0& 0\end{pmatrix},\quad A_2 = \begin{pmatrix} 0 & 1 \\ 0& 0\end{pmatrix}$$

Going through a case-by-case analysis, I think I can prove the claim for $n=2$, so there seems to be some hope...

Any help would be appreciated. Thanks!

  • 0
    (I'm rambling here) In characteristic zero, let $c_1, c_2 \neq 0.$ Then $c_1 A_1 b + c_2 A_2 b = (c_1 A_1 + c_2 A_2) b.$ But $c_1 A_1 + c_2 A_2 \neq 0,$ and so $c_1 A_1 b + c_2 A_2 b$ is non-zero as long as $b$ is in the row space of $c_1 A_1 + c_2 A_2.$ Now if we can find $c_1, c_2$ such that $c_1 A_1 + c_2 A_2$ is non-singular, then there necessarily exists such $b$??2012-07-31
  • 0
    You have $A_1 \in GL_n(F)$ and $b \in F^n$. What multiplication are you using for $A_1b$? (I'm a random noob trying to understand the problem)2012-07-31
  • 0
    @xavierm02: Just plain old [matrix multiplication](http://en.wikipedia.org/wiki/Matrix_multiplication) (identifying $F^n = F^{n\times 1}$)2012-07-31
  • 0
    @xavier: matrices act on vectors...2012-07-31
  • 0
    So you consider $M_{n,1}(F)=F^n$. Thank you :)2012-07-31
  • 1
    Proof for $n = 2$: since the problem is invariant under left multiplication by an invertible matrix, you may assume WLOG that $A_1 = I$. If $A_2 b$ is always a scalar multiple of $b = A_1 b$, then it is not hard to show that $A_2$ must be a scalar multiple of the identity, but this contradicts the assumption of linear independence.2012-07-31
  • 0
    How about this for a general approach: by contradiction, assume that there is no $b$. Then *every* $b$ must lead to the set $A_1b, A_2b,\ldots, A_nb$ to be linearly dependent, so every $b$ sits in the kernel of some matrix $B = A_k-\sum_{i=1}^m c_iA_i$. Might we possibly invoke rank-nullity here? Can we say anything about $B$ being invertible? I feel like the linear independence of columns of $A_i$'s should suffice: since $A_i$ are linearly independent, finite linear combinations must also be linearly independent, so $B$ must always be full-rank, implying $null(B) = 0$.2012-07-31
  • 0
    @Ed: the $c_i$ are allowed to depend on $b$, so $B$ also depends on $b$; it is not a single matrix. The dependence of $B$ on $b$ is also not specified to have any particular form so I am not sure how much there is to gain from this point of view (it may be useful for constructing a counterexample but it doesn't seem to be useful for constructing a proof).2012-07-31
  • 0
    @QiaochuYuan I understand that, poorly communicated. Maybe I should say every $b$ sits in the kernel of a matrix $B_b$, where $B_b$ depends on $b$. Nevertheless, the linear dependence argument of $B_b$ should still hold, no? In other words, the dependence of $B$ on $b$ may not require $B$ to have a form; however, the specific choice of $c_i$ to ensure linear dependence then dictates that the columns of $B_b$ are linear combinations of the columns of $A_i$'s. We still require the columns of $B_b$ to be linearly independent, which I am not sure how to do yet. I feel like I've seen this before.2012-07-31
  • 0
    @Ed: I think you are confusing two meanings of "linearly independent" here. The first meaning is that $A_i$ is invertible if and only if its columns consist of linearly independent _vectors._ The second meaning is the condition that the $A_i$ are themselves linearly independent _matrices._ These are distinct conditions and you seem to be conflating them.2012-07-31
  • 0
    @QiaochuYuan I am taking the definition of linear independent matrices to mean that each column of a given matrix cannot be written as a linear combination of the same column of other matrices, i.e. that the set of matrices $\left\{ A_1, A_2,\ldots, A_n \right\}$ is "linearly independent". I figured that it would be redundant to interpret "linearly independent matrix" as meaning that its own columns were L.I., as that condition is already covered by membership in $GL_n(\Bbb F)$.2012-07-31
  • 0
    @Ed: that is not the definition of linear independence of matrices. The definition is that the matrices, interpreted as vectors with $n^2$ entries, are linearly independent in the vector sense. (With your definition the problem is trivial as we can just take $b = (1, 0, 0, ...)$.)2012-07-31
  • 0
    Ah, thanks for that clarification. Do you have a source where that definition is standard for matrices? I'm not entirely certain it's not equivalent to how I'm using the term, but I need to break for lunch at some point as I am too hungry to communicate properly :)2012-07-31
  • 2
    @EdGorcenski: it's just "the" definition of linear independence in an arbitrary vector space. Linear independence is a property of a set of vectors (and, of course, the set of all matrices is a vector space) .2012-07-31
  • 0
    @MartinArgerami Right, which is what I thought. I simply don't see how vectorizing the matrix column-wise yields a different result than defining it as linear independence in the columns of each matrix. Surely if $V(A_i) \neq \sum_{k\neq i} V(A_k)$, then $\mathbf{a}_r^{(i)} \neq \sum_{k\neq i} \mathbf{a}_r^{(k)}$, with $\mathbf{a}_r$ representing the rth column.2012-07-31
  • 0
    @EdGorcenski: you have to be careful with that. For example, the matrices $$\begin{bmatrix}1&1\\1&1\end{bmatrix},\ \begin{bmatrix}1&2\\1&2\end{bmatrix}$$ are linearly independent, but the "first columns" or the "second columns" are not. Linear independence of the columns implies linear independence of the matrices, but not viceversa. So, they are different notions.2012-07-31
  • 0
    Perhaps though look at it from the other way: linear *dependence* in the matrices should mean linear dependence in the columns, then.2012-07-31
  • 0
    Of course. ${ }$2012-07-31

1 Answers 1

10

The answer is no.

Consider, for $F=\mathbb{R}$, $n=3$, $$ A_1=\begin{bmatrix}1&0&0\\0&1&0\\ 1&2&3\end{bmatrix}, \ A_2=\begin{bmatrix}1&0&0\\0&1&0\\ 2&3&1\end{bmatrix}, \ A_3=\begin{bmatrix}1&0&0\\0&1&0\\ 3&1&2\end{bmatrix}. $$ These three matrices are linearly independent, because the last three rows are. They are invertible, since the are triangular with nonzero diagonal.

For any $b=\begin{bmatrix}x\\ y\\ z\end{bmatrix}\in\mathbb{R}^3$, the three vectors we obtain are $$ A_1b=\begin{bmatrix}x\\ y\\ x+2y+3z\end{bmatrix}, \ A_2b=\begin{bmatrix}x\\ y\\ 2x+3y+z\end{bmatrix}, \ A_3b=\begin{bmatrix}x\\ y\\ 3x+y+2z\end{bmatrix}. \ $$ And for any choice of $x,y,z$, these vectors are linearly dependent. To see this, we need to find coefficients, not all zero, such that $\alpha\,A_1b+\beta\,A_2b+\gamma\,A_3b=0$. The first two rows require $\alpha+\beta+\gamma=0$. And the third row requires $(x+2y+3x)\alpha+(2x+3y+z)\beta+(2x+y+2x)\gamma=0$. As it is a homogeneous system of two equations in three variables, it will always have nonzero solutions.

  • 2
    A tiny bit simpler: $$\pmatrix{1&0&0\cr0&1&0\cr1&0&1\cr},\pmatrix{1&0&0\cr0&1&0\cr0&1&1\cr},\pmatrix{1&0&0\cr0&1&0\cr0&0&1\cr}$$ Then $yA_1b-xA_2b+(x-y)A_3b=0$ gives a non-trivial linear dependence unless $x=y=0$, in which case $A_1b-A_2b=0$.2012-08-01
  • 0
    Nice. I didn't really think about optimizing the choice (which I like to do). I just noticed that one needs only 3 coordinates to make the matrices linearly independent, and the other 6 would likely fix a lot of things if equal.2012-08-01
  • 0
    Nice. Thank you for the counterexample!2012-08-01