Return to Answer

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.$ This is the crux of this method because evaluating both sides 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 have the polynomial $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$ and 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.

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.

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 just 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 minimal polynomial is 3, $r(t)$ is at most a quadratic, $r(t) = at^2 + bt + c.$ This is the crux of this method because evaluating both sides 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. Thus if we have the polynomial $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$ and 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.

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.$ This is the crux of this method because evaluating both sides 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 have the polynomial $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$ and 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.

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 just 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 minimal polynomial is 3, $r(t)$ is at most a quadratic, $r(t) = at^2 + bt + c.$ This is the crux of this method because evaluating both sides 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. Thus if we have the polynomial $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$ and 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.

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 just 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 minimal polynomial is 3, $r(t)$ is at most a quadratic, $r(t) = at^2 + bt + c.$ This is the crux of this method because evaluating both sides 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. Thus if we have the polynomial $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$ and 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.