Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a very noob questions about generators: what algorithm do I have to follow so I can prove that a finite subset is a generator?

Here is the background story (I'll tell it all because I suck at maths and I might have understood the whole concept wrongly):

I want to know how to compute the image of a vector space morphism. I'll continue on a concrete example:

$f\colon \mathbb{R}^2 \to \mathbb{R}^2$, $f(x,y) = (x-y, 2x + y)$ is the morphism.

To find its image, I observe that $f(x,y)$ can be rewritten as $x(1,2) + y(-1,1)$. If I am correct, that means that $\mathrm{Im}(f) = \langle(1,2), (-1,1)\rangle$ (that's the notation we use for set generators). Now the question is: does the $\{(1,2), (-1,1)\}$ set generate $\mathbb{R}^2$ or not?

share|improve this question
1  
The question of when a subset generates a group is a much more difficult one than the one you are asking. What you are really asking is when a set of vectors spans a vector space. That is a much simpler question. –  Arturo Magidin Jan 3 '11 at 19:01
    
@Arturo Magidin: thank you very much for the edit, I'll try to use the math features from now on. –  cantrem Jan 3 '11 at 21:18

4 Answers 4

up vote 3 down vote accepted

Others have given you very good answers for this specific question. Let me make a few points for general problems of this type:

If you have a linear transformation $f\colon\mathbb{R}^n\to\mathbb{R}^m$, since every vector in $\mathbb{R}^n$ can be written as a linear combination of the standard basis vectors: $$\begin{array}{rcl} \mathbf{e}_{1} &=& (1,0,0,\ldots,0)\\ \mathbf{e}_{2} &=& (0,1,0,\ldots,0)\\ &\cdots&\\ \mathbf{e}_n &=& (0,0,0,\ldots,1), \end{array}$$ then the span of $f$ equals $\langle f(\mathbf{e}_1,\ldots,f(\mathbf{e}_2)\rangle$. In the example you have, this is essentially what you did, since $f(1,0) = (1,2)$ and $f(0,1)=(-1,1)$. Second, to find the span of a set of vectors, you can use Gaussian elimination. Put them as rows of a matrix and perform Gaussian elimination (or Gauss-Jordan elimination). The span of the original vectors equals the span of the rows of the matrix, and elementary row operations does not change the span of the rows. The rank will give you the dimension of the image, and if you only want to know if the image is all of $\mathbb{R}^m$, then you just need to see if the rank of the reduced row echelon form is $m$.

But it is more common express the function as an $m\times n$ matrix: in the $i$th column, you write down the image of $\mathbf{e}_i$; the image of $f$ is then the span of the columns of this matrix. In your example, we would have $$\left(\begin{array}{rr} 1 & -1\\ 2 & 1 \end{array}\right)$$ (the first column is the image of $(1,0)$; the second column is the image of $(0,1)$).

Since the dimension of the columnspace is the same as the dimension of the rowspace, you can still use elementary row operations to figure out the rank. However, elementary row operations may change the columnspace (not the dimension of the columnspace, but the columnspace itself yes). So you have to be careful there. Here, it is very easy: subtracting twice the first row from the second row, then dividing the second row by $3$, and adding it to the first row we get: $$\left(\begin{array}{rr} 1 & -1\\ 2 & 1 \end{array}\right) \to \left(\begin{array}{rr} 1 & -1\\ 0 & 3 \end{array}\right)\to\left(\begin{array}{rr} 1 & -1\\ 0 & 1 \end{array}\right) \to \left(\begin{array}{rr} 1 & 0\\ 0 & 1 \end{array}\right).$$ Since the reduced row echelon form has rank $2$, the columnspace of the original has dimension $2$, so you conclude that $\dim(\mathrm{Im}(f)) = 2$. Since the only subspace of $\mathbb{R}^2$ that has dimension $2$ is $\mathbb{R}^2$ itself, you are done.

share|improve this answer
    
Amazing answer, thank you. Unfortunately, I still need to ask some questions: You said that I can "Put them as rows of a matrix and perform Gaussian elimination (or Gauss-Jordan elimination)" - is this always necessary? I mean: we have to figure out the rank of the original matrix (in this case, we could simply calculate (1 * 1) - (2 * -1) which does not equal 0, which gives us a rank of 2. Is it the same? And can you use the Gaussian elimination process to get a simplified set of vectors (in case they are dependent of each other)? –  cantrem Jan 3 '11 at 21:33
    
@Cantrem: No, you don't need to do Gauss-Jordan if all you want is to know the rank; the advantage of Gauss-Jordan is that it will yield, in the end, a basis for the rowspace (as opposed to just a spanning set), and it will be a "nice basis": one that makes it easy to check if a particular vector is or is not in the span. But if all you want is to know the rank, then you can stop as soon as you can figure out the rank by any valid means. –  Arturo Magidin Jan 3 '11 at 22:15
    
I see. I think now I'm getting really close to a decent understanding. If you can help me with the last question ("And can you use the Gaussian elimination process to get a simplified set of vectors (in case they are dependent of each other)?") I promise not to bother you again (or at least until my exams will be over). –  cantrem Jan 4 '11 at 6:26
    
@cantrem: I though I answered. If you do Gauss-Jordan correctly, you will end up with a bunch of rows that are obviously linearly independent (they have the pivots in different columns, and all other rows have zeroes in those columns), and possibly some rows that are zero The basis for the original rowspace consists of the rows that are not zero. If you do get some zero rows, your original list was linearly dependent. (cont...) –  Arturo Magidin Jan 4 '11 at 6:30
    
@cantrem: (cont...) And if you use the more standard set up as above where you want the columnspace, then you do Gauss-Jordan, note which columns have the pivots, and you pick the columns in the original matrix that correspond to the columns where the pivots are in the reduced-row-echelon form. –  Arturo Magidin Jan 4 '11 at 6:32

If you want to know whether the two vectors span the plane, just use the standard results in this case: they span the plane if and only if they are linearly independent, or the $2$-by-$2$ matrix is invertible, and so on.

Alternatively you can just show that for every point in the plane there exists the required $x$ and $y$ by solving a pair of simultaneous equations.

share|improve this answer
    
Not necessarily. In the example I gave, yes. But there are other types of problems, for example determining the subspaces generated by some specific sets of vectors (in R^2, R^3 and so on). That's why I was looking for a more general answer. Should I open another thread with this question? –  cantrem Jan 4 '11 at 6:30

You compute the rank of the matrix whose entries are the coordinates of the vectors in the set (with respect to some basis, say the canonical basis in $\mathbf{R}^n$). The set generates the space iff the rank equals the dimension of the space. In your example, you want the rank to be 2. The rank of a matrix can be found using Gaussian elimination.

share|improve this answer

HINT $\ $ Two vectors span $\rm\:\mathbb R^2\:$ iff they are nonzero and have different slopes.

Generally you can test if $f$ is onto by computing the rank of the matrix of $f$.

share|improve this answer

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.