ATAR Notes: Forum

Uni Stuff => Science => Faculties => Mathematics => Topic started by: acinod on April 15, 2012, 01:53:35 pm

Title: Proving subspaces and spanning sets
Post by: acinod on April 15, 2012, 01:53:35 pm: 1. Prove that the following subset S of Z₂⁵ is a subspace of Z₂⁵and calculate its dimension. The subset S consists of all vectors with an even number of 1s, e.g. (1, 0, 1, 0, 0) and (0, 0, 0, 0, 0) are both in S while (1, 0, 1, 0, 1) is not in S.

2. Prove that the following set of vectors: { $\Big(\begin{matrix}2 & 1\\0 & 0\end{matrix}\Big)$ , $\Big(\begin{matrix}0 & 0\\2 & 1\end{matrix}\Big)$ , $\Big(\begin{matrix}3 & -1\\0 & 0\end{matrix}\Big)$ , $\Big(\begin{matrix}0 & 0\\3 & 1\end{matrix}\Big)$ } spans the vector space M_2,2.

Cheers.
Title: Re: Proving subspaces and spanning sets
Post by: kamil9876 on April 16, 2012, 12:04:06 am: You could probably post this in the math section, this is not only taught in uom.

1.) So it's clearly not empty (you've written down an example). If $v \in S$ then $0.v$ is the zero vector, hence it has an even number of $1$ 's; while $1.v=v$ and so it has an even number of ones. So it is closed under scalar multiplication.

To show it is closed under addition suppose that $v=(v_1,v_2,v_3,v_4,v_5)$ and $w=(w_1,w_2,w_3,w_4,w_5)$ are both in $S$ . Let $I=\{ i | v_i=1 \}$ and $J=\{j |w_j =1\}$ . Let $K=\{k | v_k+w_k=1\}$ , show that $K=I\cup J - I\cap J$ (set difference). Hence the size of $K$ is $|K|=|I \cup J|-|I\cap J|=|I|+|J|-2|I\cap J|$ and this is even (it is the sum of even integers). Therefore $v+w \in S$

2) Just use Gaussian Elimination?
Title: Re: Proving subspaces and spanning sets
Post by: kamil9876 on April 16, 2012, 09:29:43 pm: Which part didn't you understand (apart from me forgetting to calculate the dimension)?
Title: Re: Proving subspaces and spanning sets
Post by: kamil9876 on April 16, 2012, 10:37:45 pm: Ahh right sorry ok, let me write it out in words:

Let $I$ be the set of all $i$ such that $v_i$ is $1$

Let $J$ be the set of all $j$ such that $w_j$ is $1$

Let $K$ be the set of all $k$ such that $v_k+w_k$ is $1$

Example: if $v=(1,1,0,0,0)$ and $w=(0,1,1,1,1)$ then $I=\{1,2\}$ , $J=\{2,3,4,5\}$ and since $v+w=(1,0,1,1,1)$ then $K=\{1,3,4,5\}$ .

For any set $A$ I will write $|A|$ to be the number of elements in $A$ , so in the above example $|I|=2$ , $|J|=4$ and $|K|=4$ .

So clearly the point of this problem is to show that $|K|$ is always even if $|I|$ and $|J|$ both are even.
Title: Re: Proving subspaces and spanning sets
Post by: TrueTears on April 18, 2012, 08:11:17 pm: Quote from: Nirbaan on April 18, 2012, 07:55:53 pm
How did you get from
$|K|=|I \cup J|-|I\cap J|$
to
$=|I|+|J|-2|I\cap J|$

but everything else makes perfect sense, thanks!
$|I \cup J| = |I| + |J| - |I \cap J|$
Title: Re: Proving subspaces and spanning sets
Post by: kamil9876 on April 18, 2012, 08:13:07 pm: This is a general property of sets $|A \cup B|=|A|+|B|-|A \cap B|$ . (in vce you may have seen the probability version of this)?

Loosely speaking, you subtract off the intersection since you counted those elements twice.
Title: Re: Proving subspaces and spanning sets
Post by: jeppikah on April 18, 2012, 09:21:26 pm: So how do you go about calculating dimension?
Title: Re: Proving subspaces and spanning sets
Post by: kamil9876 on April 19, 2012, 12:41:32 am: There are two possible approaches:

1) Find a basis - this is pretty much using the definition

2) Find how many elements are in the space - an m-dimensional vector space over $\mathbb{F}_2$ has $2^m$ elements, hence if you can count how many elements there are then just take $log_2$ to find the dimension.

So using approach 2) how many different such sequences vectors are there with an even number of 1's? Well you can choose the first four entries to be anything you like, and then there is a unique choice for the last entry which makes you have an even number of 1's in total (more precisely, if out of the first four entries, there is an odd number of 1's, then the last entry must be a 1. If however out of the first four entries, there is an even number of 1's, then the last entry must be a 0). So you see there is a one to one correspondence between vectors with 4 entries and vectors with 5 entries with even number of 1's. Hence there are $2^4$ such vectors so the dimension is $4$

Here is an approach using 1), finding an explicit basis: (1,1,0,0,0),(1,0,1,0,0),(1,0,0,1,0),(1,0,0,0,1) I'll leave it as an exercise to check that it is indeed a basis (there is a shortcut: it is easy to check linear independence(put it in a matrix and see), and if it spans something that is not the space we're after, then it must span something bigger and a bigger thing must be 5 dimensional hence the whole space, which can't occur)
Title: Re: Proving subspaces and spanning sets
Post by: Mao on April 19, 2012, 01:10:08 am: > I have spent the whole day challenging various people's paradigms. I guess this is my relaxation.

Allow me to offer my view on the first subset problem (in original post), on how to prove S is a subspace.

Define the length of a quantity in $Z_2^5$ as the sum of digits.

The length of quantities in $S$ are either 0, 2 or 4. Denote these sets as $L0,\, L2\mbox{ and }L4$ . Let's ignore $L0$ for now, as the logic here is rather trivial.

Any $L4$ can be written as various arrangements of $L2+L2$ . Any addition in $S$ can thus be written as sums of $L2$ . To show that addition is closed, we need to:
- Show that $L2+L2\in S$
- Consider if we have $\alpha, \beta, \gamma \in L2$ , and we wish to perform $\alpha + \beta + \gamma$ . No matter how we arrange $\alpha,\beta\mbox{ and }\gamma$ , we'll always end up with the possibility of having a $L4+L2$ addition on our hand. So, we must also show that $L4+L2\in S$

Showing that $L2+L2\in S$ is simple. We have 3 cases: none of the digits line up, in which case we get a $L4$ ; only one of the digits line up, in which case we get a $L2$ ; both digits line up, in which we get a $L0$ .

Showing that $L4+L2\in S$ is also simple. We have two cases: both digits in $L2$ line up with digits in $L4$ , we get a $L2$ ; only one digit of $L2$ lines up with $L4$ , in which case we get a $L4$ .

And then we throw in the bits about adding L0 doesn't affect anything. QED.
Title: Re: Proving subspaces and spanning sets
Post by: Mao on April 19, 2012, 01:28:16 am: Quote from: Nirbaan on April 16, 2012, 09:26:11 pm
Find the spanning set for the following subspace of R^3

{(a+c, c-b, 3c):a,b,c E R}
(a,0,0)+(0,-b,0)+(c,c,3c)

One possible spanning set is (1,0,0), (0,1,0), (1,1,3)
Title: Re: Proving subspaces and spanning sets
Post by: kamil9876 on April 19, 2012, 12:50:02 pm: Actually just realised there is a much simpler way (if you know what a Linear Transformation is).

Consider the function $T(v_1,v_2,v_3,v_4,v_5)=v_1+v_2+v_3+v_4+v_5$ . Then it's easy to check that this function is a linear transformation. Moreover the set $S$ of elements with even number of $1$ 's is indeed the kernel (a.k.a nullspace) of this linear transformation. And so it is indeed a subspace. Finding the dimension is easy since the matrix of $T$ with respect to the standard bases is just [1 1 1 1 1]