Diagonalization: Can you spot a trick to avoid tedious computation?

I am studying for my graduate qualifying exam and unfortunately for me I have spent the last two years studying commutative algebra and algebraic geometry, and the qualifying exam is entirely 'fundamental / core' material - tricky multivariable calculus and linear algebra questions, eek!

Here is the question from an old exam I am working on. Please note, how to solve the problem is not my specific question. After I introduce the problem, I will ask my specific questions about the problem below.

No Calculators. Let $$M = \begin{bmatrix} 2 & 0 & 0 \\ 1 & 4 & 2 \\ 0 & -2 & -1\\ \end{bmatrix}$$ 1) Find the determinant of $M$,

2. Find the eigenvalues and associated eigenvectors of $M$,

3. Calculate $$M^{2013} \cdot \begin{bmatrix}1\\1\\1\\\end{bmatrix}.$$

My issue is that with computational problems on an exam where calculators aren't allowed I always expect that either:

1. there will be a trick to sidestep nasty calculations by hand,
2. the problem will be contrived in such a way that the computation goes very easily.

This seems to be the case in part 1 and part 2 of the problem since:

1. The determinant of $M$ can very easily be found by cofactor across row 1 to get $\mathrm{det}(M) = 2(-4+4) = 0$, or by inspection we see column 2 is quite visibly a scalar multiple of column 3 so that $\mathrm{det}(M) = 0$.

2. Since $\mathrm{det}(M) = 0$ we know 0 is an eigenvalue. Noting the dependence relation between column 2 and column 3 allows us to easily read off an eigenvector for $\lambda = 0$. Further, manually computing $\mathrm{det}(M - \lambda I)$ is again computationally easy because of the 0's across row 1. We get $p_{M}(t) = \lambda(2-\lambda)(\lambda - 3)$. Solving for the corresponding eigenvectors is also fairly fast.

Now - part 3 starts off fine. Considering part 2 it is practically implied from context clues that we are intended to diagonalize this matrix $M$, as the only thing needed at this point is the inverse of the matrix of eigenvectors. The computation is when I go into a whirlwind because it does not flow as easily as the previous computations. In part 2 we had a degree three polynomial we wanted roots of, and of course it split into linear factors. Now I am inverting a 3x3 matrix by hand and getting all entries as ratios? On the exam, this will panic me. Time is definitely an issue and I need to learn how to not waste it. I immediately start restudying the problem trying to see if there is some way around computing a 3 x 3 inverse by hand. One other approach I took, since I am just studying right now and not worried about time, was trying to express the vector $(1,1,1)^T$ as a linear combination of eigenvectors, say $$(1,1,1)^T = a_1v_1 + a_2v_2 + a_3v_3$$ with suitably chosen eigenvectors $v_1, v_2, v_3$, since then $$M^{2013}(a_1 v_1 + a_2 v_2 + a_3 v_3) = a_2 \lambda_2^{2013}v_2 + a_3 \lambda_3^{2013} v_3.$$

Finding the linear combinations of eigenvectors seems to be no more or less easy than inverting the matrix of eigenvectors.

Although I took a graduate abstract linear algebra course, I also worked in a tutoring center for years where I tutored problems like this without advanced methods - thus when I see questions like this, the method that immediately comes to mind is the classic one - diagonalize.

Does anyone see any tricks to avoid nasty computation by hand in the problem above?

More generally (I am sure lots of other users have taken graduate qual exams, and might have feedback here) does anyone have exam advice, perhaps a systematic way to decide if I should simply commit to doing the computation, and try to do it carefully yet as fast as possible, or halt myself in my tracks and say "they wouldn't expect me to do this computation by hand, I should study the problem and see if there is a way around this."

Thank you.

Edit: I suppose I may slightly be misusing this site since I know how to solve my problem, and my question is more geared towards exam skills? Part of my question even borders psychology... This is a bit of a philosophical conundrum whether my question is appropriate for the site. But, my exam is tomorrow so I will risk it! If it gets closed, so be it :)

Solution 1:

This answer is a more detailed walk through of the method outlined by @yixing in the comments. I present it more verbosely than I would on the exam for the aid of anyone else who reads it.

From part 2 of the problem we have already discovered that $M$ has 3 distinct eigenvalues (thus diagonalizable) and also have found the characteristic polynomial $p_m(t) = x(2-x)(3-x).$ Since $k[t]$ is a Euclidean domain, we know that for the polynomials $t^{2013}$ and $p_m(t)$, there exists $q(t)$ and $r(t)$ such that $$t^{2013} = p_m(t)q(t) + r(t), \hspace{5mm}(1)$$ where $\mathrm{deg}(r(t)) < \mathrm{deg}(p_m(t)).$ Note that since the degree of the characteristic polynomial is 3, $r(t)$ is at most a quadratic, $r(t) = at^2 + bt + c.$ The degree of $r(t)$ being at most two will ultimately be the crux of why this method is computationally superior to diagonalizing the matrix $M$, for evaluating both sides of (1) at the matrix M yields $$M^{2013} = p_m(M)q(M) + r(M),$$ thus $$M^{2013} = r(M) = aM^2 + bM + cI.$$ This final line can be justified either by invoking the Cayley-Hamilton theorem, or by noting that since the matrix is diagonalizable with 3 distinct eigenvalues, the characteristic polynomial and minimal polynomial are equivalent and by definition the minimal polynomial vanishes on $M$. Thus if we solve for the coefficients of $r(t)$, the desired matrix / vector multiplication can be computed easily. By evaluating line (1) at t = 0,2,3 we discover that $c = 0$, then get an 'easy to solve' 2x2 system for $a,b$ yielding $a = 3^{2012} - 2^{2012}$, $b = 2^{2012} + 2^{2013} - 2\cdot 3^{2012}$.

Now let $v = (1,1,1)^{T}$, then it is easily computed mentally that $Mv = (2,7,-3)^T$ and $M^2v = (4,24,-11)^T$. So we have \begin{align*} M^{2013}\cdot v &= aM^2v + bMv\\ &= a(2,7,-3)^T + b(4,-24,-11)^T.\\ \end{align*}

Since the values for $a,b$ were found above, I see no reason to simplify further.

A huge thanks to @yixing for the suggestion of this method. The method is considerably faster than computing an inverse by hand, and is actually quite robust.

Solution 2:

Here is a slightly different approach. In part 2, you have already determined that $M$ has three distinct eigenvalues $2, 3, 0$. Therefore $M$ is diagonalisable and by Lagrange interpolation, \begin{align} M^{2013} &=2^{2013}\frac{M-0}{2-0}\frac{M-3}{2-3} + 3^{2013}\frac{M-2}{3-2}\frac{M-0}{3-0}\\ &=3^{2012}(M^2-2M)-2^{2012}(M^2-3M). \end{align} Now, by direct calculation, $$ u:=M\pmatrix{1\\ 1\\ 1}=\pmatrix{2\\ 7\\ -3}, \quad v:=M^2\pmatrix{1\\ 1\\ 1}=M\pmatrix{2\\ 7\\ -3}=\pmatrix{4\\ 24\\ -11}. $$ Therefore \begin{align} M^{2013}\pmatrix{1\\ 1\\ 1} &=3^{2012}(v-2u)-2^{2012}(v-3u)\\ &=3^{2012}\pmatrix{0\\ 10\\ -5}-2^{2012}\pmatrix{-2\\ 3\\ -2}. \end{align} Neither $M^{2013}$ nor any eigenvector of $M$ are needed here. There is also no need to solve any messy system of equations. Computations are few and much less error-prone.