Page 1 of 1

8767 #53 and #61

Posted: Sat Oct 24, 2009 4:36 am
by goodtrain
I have no idea about these two, lin alg is a blur. Thanks for any help.

61. I does not equal A does not equal -I, where I is the identity matrix and A is a real 2x2. If A = A^(-1) (as in A is its own inverse), then the trace of A is
(a) 2
(b) 1
(c) 0(answer)
(d) -1
(e) -2

53. Let V be a vector space, under usual operations, of real polynomials that are of degree at most 3. Let W be the subspace of all polynomials p(x) in V such that p(0) = p(1) = p(-1) = 0. Then dim V + dim W =
(a) 4
(b) 5(answer)
(c) 6
(d) 7
(e) 8

Re: 8767 #53 and #61

Posted: Sat Oct 24, 2009 5:16 am
by diogenes
goodtrain wrote:
61. I does not equal A does not equal -I, where I is the identity matrix and A is a real 2x2. If A = A^(-1) (as in A is its own inverse), then the trace of A is
(a) 2
(b) 1
(c) 0(answer)
(d) -1
(e) -2

Okay, A is a Unitary matrix and going even further since all the entries are real we have an orthogonal matrix. Since this is a 2x2 matrix we have two eigenvalues. Orthogonal matrix implies that the eigenvalues are modulus 1. Set:

$$\[
A =
\left[ {\begin{array}{cc}
a & b
& c & d
\end{array} } \right]
\]$$

So, we have that:

$$\[
A^{-1} =
\left[ {\begin{array}{cc}
-d & b
& c & -a
\end{array} } \right]
\]$$

( we note that det(A) is either +1 or -1 , which will just "flip" the order of the eigenvalues).
Also we have that $$det(A) = A^T$$:

$$\[
A^{-1} =
\left[ {\begin{array}{cc}
a & c
& b & d
\end{array} } \right]
\]$$

So, we see that a = -d.

Now we can use the fact that eigenvalues are either -1 or 1.
Finally, we have that the trace is sum of the eigenvalues so we get 1+-1=0, or just note the Trace(A) = a+d = -d+d = 0.

Re: 8767 #53 and #61

Posted: Sun Oct 25, 2009 7:55 pm
by joey
goodtrain wrote:I have no idea about these two, lin alg is a blur. Thanks for any help.

61. I does not equal A does not equal -I, where I is the identity matrix and A is a real 2x2. If A = A^(-1) (as in A is its own inverse), then the trace of A is
(a) 2
(b) 1
(c) 0(answer)
(d) -1
(e) -2

53. Let V be a vector space, under usual operations, of real polynomials that are of degree at most 3. Let W be the subspace of all polynomials p(x) in V such that p(0) = p(1) = p(-1) = 0. Then dim V + dim W =
(a) 4
(b) 5(answer)
(c) 6
(d) 7
(e) 8
For #61, you can get by without knowing all that jazz by looking for an idempotent matrix other than I or -I and taking its trace. Your work won't prove the general case, but it will get you the correct answer quickly. In this case,
$$\left( {\begin{array}{cc}
0 & 1 \\
1 & 0 \\
\end{array} } \right)$$
works nicely and has trace 0. When faced with unfamiliar problems, I frequently construct examples and test them on the fly like this. Usually a single example will reduce the answer pool to two or three choices, making it advantageous to guess. Sometimes the example will give the correct answer immediately, as was the case here.

I'm no expert on #53, either, but I have a solution. As a vector space, V might as well be $$\mathbb{R}^4$$, so it has dimension 4. Our problem is basically to find dim W.
We can get a feel for W by manipulating its generic element
$$p(x) = a_3 x^3 + a_2 x^2 + a_1 x + a_0.$$
Since p(0)=0, $$a_0 = 0$$. Similarly, evaluating p(1) and p(-1) gives the system of equations
$${\begin{array}{r}
a_3 + a_2 + a_1 = 0 \\ -a_3 + a_2 - a_1 = 0 \\ \end{array}}$$
Row-reducing the augmented matrix gives
$$\left( \begin{array}{cccc}
1 & 1 & 1 & 0 \\ -1 & 1 & -1 & 0 \\ \end{array}\right) \sim \left(\begin{array}{cccc}
1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ \end{array}\right)$$
In other words, $$a_2 = 0$$ and $$a_1 = -a_3$$. Hence, each element of W can be written
$$p(x) = \lambda \left(x^3 - x\right), \lambda \in \mathbb{R},$$
and W has dimension at most 1. To be rigorous, we should check that dim W is at least 1. Setting $$\lambda = 1$$ gives a non-zero element of W, which is sufficient (I do this step quickly in my head). Hence, W has dimension exactly 1, and the answer is 5. There might be a slicker way to do this, but I don't know it.

Re: 8767 #53 and #61

Posted: Sun Oct 25, 2009 10:03 pm
by diogenes
joey wrote:
I'm no expert on #53, either, but I have a solution. As a vector space, V might as well be $$\mathbb{R}^4$$, so it has dimension 4. Our problem is basically to find dim W.
We can get a feel for W by manipulating its generic element
$$p(x) = a_3 x^3 + a_2 x^2 + a_1 x + a_0.$$
Since p(0)=0, $$a_0 = 0$$. Similarly, evaluating p(1) and p(-1) gives the system of equations
$${\begin{array}{r}
a_3 + a_2 + a_1 = 0 \\ -a_3 + a_2 - a_1 = 0 \\ \end{array}}$$
Row-reducing the augmented matrix gives
$$\left( \begin{array}{cccc}
1 & 1 & 1 & 0 \\ -1 & 1 & -1 & 0 \\ \end{array}\right) \sim \left(\begin{array}{cccc}
1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ \end{array}\right)$$
In other words, $$a_2 = 0$$ and $$a_1 = -a_3$$. Hence, each element of W can be written
$$p(x) = \lambda \left(x^3 - x\right), \lambda \in \mathbb{R},$$
and W has dimension at most 1. To be rigorous, we should check that dim W is at least 1. Setting $$\lambda = 1$$ gives a non-zero element of W, which is sufficient (I do this step quickly in my head). Hence, W has dimension exactly 1, and the answer is 5. There might be a slicker way to do this, but I don't know it.
Actually, it is even simpler. The subspace is the nullspace and the mapping is onto $$R^3$$. :)

Re: 8767 #53 and #61

Posted: Tue Oct 27, 2009 1:21 pm
by joey
diogenes wrote: Actually, it is even simpler. The subspace is the nullspace and the mapping is onto $$R^3$$. :)
Can you say more about this? To what function are you referring?

Re: 8767 #53 and #61

Posted: Tue Oct 27, 2009 9:23 pm
by diogenes
From here it is just using the rank nullity thrm: rank poly is three and W is the kernal of V so it has dim 4-3 =1.

http://en.wikipedia.org/wiki/Rank%E2%80 ... ty_theorem

Re: 8767 #53 and #61

Posted: Tue Oct 27, 2009 9:31 pm
by joey
But what's the linear transformation in this case? Is there a standard way to map polynomials to $$\mathbb{R}^n$$? I'm in unfamiliar territory.

Re: 8767 #53 and #61

Posted: Tue Oct 27, 2009 9:42 pm
by joey
Oh I get it! Okay, we're mapping $$p(x) \mapsto \left({\begin{array}{c} p(1) \\ p(-1) \\ p(0) \\ \end{array}}\right)$$. Is this a linear transformation, though? ... Yep, it's easy to check. And we can pick the constants of p(x) so that our mapping goes to any vector in $$\mathbb{R}^3$$, so its rank is 3. Clever! :)

Re: 8767 #53 and #61

Posted: Wed Oct 28, 2009 2:08 am
by diogenes
Something I have to remind myself is to make sure not to get bogged down in "details" (yes i know details are what is it about in a big picture sense, but not on multiple choice test). Maybe this will be helpful to you?

Once, you get the "real" question behind the question, e.g., "oh this is really a rank nullity question" your should feel pretty confident in you next actions. :D

Re: 8767 #53 and #61

Posted: Wed Oct 28, 2009 7:57 am
by joey
I think it will, yes. I "know" the Rank-Nullity Theorem, so I guess I ought to have made the connection between vector space, dimension, function, and zero right away. It may be that I'm not used to seeing vector spaces of polynomials, and that threw me off. I'll keep an eye out for this one on the test. Thanks! :D

Re: 8767 #53 and #61

Posted: Tue Nov 03, 2009 2:30 am
by kosuke
Why can't we just say because we know that p(0)=p(1)=p(-1)=0 that W is all scalar multiples of p(x)=x(x+1)(x-1)=x^3-x, and thus only has dim=1?

That's what I did, but it seems too simple after reading other people's solutions...
Did I do something wrong?

Re: 8767 #53 and #61

Posted: Tue Nov 03, 2009 7:57 am
by joey
kosuke wrote:Why can't we just say because we know that p(0)=p(1)=p(-1)=0 that W is all scalar multiples of p(x)=x(x+1)(x-1)=x^3-x, and thus only has dim=1?

That's what I did, but it seems too simple after reading other people's solutions...
Did I do something wrong?
Haha! No, that works perfectly! :)

Re: 8767 #53 and #61

Posted: Mon Nov 07, 2011 3:27 pm
by rahulshr
I think easiest way to solve #61 is -
A=A^-1 => A^2 = I

Using - Characteristic equation of 2x2 matrix is: x^2 - x*tr(A) + det(A) = 0, and a matrix satisfies its own characteristic equation.

This means the characteristic equation for A is = x^2=1, or x^2-1 = 0...since coefficient of x^1 is 0, so trace of A = 0.

Re: 8767 #53 and #61

Posted: Thu Nov 10, 2011 10:57 am
by Hom
rahulshr wrote:I think easiest way to solve #61 is -
A=A^-1 => A^2 = I

Using - Characteristic equation of 2x2 matrix is: x^2 - x*tr(A) + det(A) = 0, and a matrix satisfies its own characteristic equation.

This means the characteristic equation for A is = x^2=1, or x^2-1 = 0...since coefficient of x^1 is 0, so trace of A = 0.
this is awesome

Re: 8767 #53 and #61

Posted: Thu Nov 10, 2011 12:09 pm
by owlpride
This means the characteristic equation for A is = x^2=1, or x^2-1 = 0...since coefficient of x^1 is 0, so trace of A = 0.
Careful. The equation A^2 - 1 = 0 tells you that the characteristic polynomial of A is one of the following:

a) (x-1)^2 = x^2 - 2x + 1
b) (x+1)^2 = x^2 + 2x + 1
c) (x-1)*(x+1) = x^2 - 1

You need the hypothesis that A is not I or -I to conclude that you are in case (c). [Think this way: If A was the identity matrix, then the trace of A is 2 and not 0, so you certainly need to use the hypothesis somewhere.]

In case someone wants a short refresher on minimal and characteristic polynomials:

The minimal polynomial of a matrix is the least polynomial p(x) so that p(A) = 0. If q(x) is any other polynomial equation with q(A) = 0, then p|q. In this problem we know that A^2 - 1 = 0, so the minimal polynomial of A divides x^2 - 1 = (x-1)(x+1). So the minimal polynomial is either (x-1), (x+1) or (x-1)*(x+1). Now we need a relationship between the minimal and the characteristic polynomials:

- both polynomials are a product of (x - Eigenvalue) factors
- the minimal polynomial divides the characteristic polynomial (since the 0 = characteristic polynomial evaluated at A)

More precisely: the multiplicity of an (x-a) factor in the minimal polynomial is the size of the largest Jordan block of the Eigenvalue a in the Jordan Normal Form, whereas the multiplicity of (x-a) in the characteristic polynomial is sum of the sizes of all Jordan blocks of a.

For example, if the minimal polynomial of an nxn matrix is (x-1), then the characteristic polynomial is (x-1)^n. If the minimal polynomial is (x-1)*(x+1), then the characteristic polynomial is (x-1)^k * (x+1)^(n-k).

It takes some care to go back and forth between minimal and characteristic polynomials. Two matrices with the same characteristic polynomial may have distinct minimal polynomials, or they may have the same minimal polynomial with distinct characteristic polynomials. For example, the matrices

$$A = \left( \begin{array}{ll}1 & 0 \\ 0 & 1\end{array} \right), B = \left( \begin{array}{ll}1 & 1 \\ 0 & 1\end{array} \right)$$

both have characteristic polynomial (x-1)^2, but the minimal polynomial of A is (x-1) while the minimal polynomial of B is (x-1)^2.

On the other hand, the diagonal matrices

$$A = \left( \begin{array}{lll}1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 2\end{array} \right), B = \left( \begin{array}{lll}1 & 0 & 0\\ 0 & 2 & 0 \\ 0 & 0 & 2\end{array} \right)$$

have the same minimal polynomial (x-1)*(x-2), but different characteristic polynomials (x-1)^2 * (x-2) and (x-1) * (x-2)^2.

Re: 8767 #53 and #61

Posted: Fri Nov 11, 2011 4:12 am
by rahulshr
Thanks owl.
Looks like my understanding of characteristic equations is half cooked, as if there is any doubt :).... twice it has backfired, but somehow the answer choice I got was correct ;).... (have brushed linear Algebra after decade!!, specifically for GRE).

Re: 8767 #53 and #61

Posted: Fri Nov 11, 2011 4:15 am
by rahulshr
owlpride wrote:
This means the characteristic equation for A is = x^2=1, or x^2-1 = 0...since coefficient of x^1 is 0, so trace of A = 0.
Careful. The equation A^2 - 1 = 0 tells you that the characteristic polynomial of A is one of the following:

a) (x-1)^2 = x^2 - 2x + 1
b) (x+1)^2 = x^2 + 2x + 1
c) (x-1)*(x+1) = x^2 - 1

You need the hypothesis that A is not I or -I to conclude that you are in case (c). [Think this way: If A was the identity matrix, then the trace of A is 2 and not 0, so you certainly need to use the hypothesis somewhere.]

In case someone wants a short refresher on minimal and characteristic polynomials:

The minimal polynomial of a matrix is the least polynomial p(x) so that p(A) = 0. If q(x) is any other polynomial equation with q(A) = 0, then p|q. In this problem we know that A^2 - 1 = 0, so the minimal polynomial of A divides x^2 - 1 = (x-1)(x+1). So the minimal polynomial is either (x-1), (x+1) or (x-1)*(x+1). Now we need a relationship between the minimal and the characteristic polynomials:

- both polynomials are a product of (x - Eigenvalue) factors
- the minimal polynomial divides the characteristic polynomial (since the 0 = characteristic polynomial evaluated at A)

More precisely: the multiplicity of an (x-a) factor in the minimal polynomial is the size of the largest Jordan block of the Eigenvalue a in the Jordan Normal Form, whereas the multiplicity of (x-a) in the characteristic polynomial is sum of the sizes of all Jordan blocks of a.

For example, if the minimal polynomial of an nxn matrix is (x-1), then the characteristic polynomial is (x-1)^n. If the minimal polynomial is (x-1)*(x+1), then the characteristic polynomial is (x-1)^k * (x+1)^(n-k).

It takes some care to go back and forth between minimal and characteristic polynomials. Two matrices with the same characteristic polynomial may have distinct minimal polynomials, or they may have the same minimal polynomial with distinct characteristic polynomials. For example, the matrices

$$A = \left( \begin{array}{ll}1 & 0 \\ 0 & 1\end{array} \right), B = \left( \begin{array}{ll}1 & 1 \\ 0 & 1\end{array} \right)$$

both have characteristic polynomial (x-1)^2, but the minimal polynomial of A is (x-1) while the minimal polynomial of B is (x-1)^2.

On the other hand, the diagonal matrices

$$A = \left( \begin{array}{lll}1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 2\end{array} \right), B = \left( \begin{array}{lll}1 & 0 & 0\\ 0 & 2 & 0 \\ 0 & 0 & 2\end{array} \right)$$

have the same minimal polynomial (x-1)*(x-2), but different characteristic polynomials (x-1)^2 * (x-2) and (x-1) * (x-2)^2.
The question did mention that A is not Identity matrix.. does my solution make sense now?

Re: 8767 #53 and #61

Posted: Fri Nov 11, 2011 12:02 pm
by owlpride
I know that the question stated it as an hypothesis. I just wanted to make sure that readers are aware that you actually used the hypothesis to get the characteristic polynomial of A. Here's the catch:

Suppose that A is an nxn matrix, and p(x) is a monic nth degree polynomial with p(A) = 0. It does NOT in general follow that p is the characteristic polynomial of A. All you can conclude is that the minimal polynomial of A (which usually has degree < n) divides p. And since the minimal polynomial also divides the characteristic polynomial, you can conclude that p has some factors in common with the characteristic polynomial. Which factors? Here's where the hypothesis that A is not I or -I was used in your solution.

Re: 8767 #53 and #61

Posted: Fri Nov 11, 2011 1:52 pm
by owlpride
That being said, if I were to encounter this question on the actual GRE, I would not waste time with abstract reasoning and produce explicit examples instead. Which 2x2 matrices satisfy A = A^(-1)? I can think of 3 off the top of my head: I, -I and a diagonal matrix with diagonal entries +1 and -1. They have traces 2, -2 and 0 respectively. The hypothesis says to ignore I and -I. Since I only get to pick a single answer for the trace, 0 must be the correct answer because I have a valid example of a trace-0 matrix satisfying all of the hypotheses.