1
$\begingroup$

$f:\Bbb R^2\to \Bbb R^2$ given by $$f(x)=\begin{bmatrix}\frac12&0\\0&\frac13\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}$$ We can determine if this is a contraction map by showing that $\|Ax\|\leq k \lt 1$ when $\|x\|=1$

Therefore we can take $x=(\cos t,\sin t)$

and hence $$Ax=\begin{pmatrix}\frac12 \cos t\\\frac13\sin t\end{pmatrix}$$ $$\|Ax\|^2=\frac14\cos^2t+\frac19\sin^2 t\leq \frac14$$ And hence $\|Ax\|\leq\frac12$, and thus this is a contraction.


What about in the case where we have a $3\times 3$ matrix? $$f(x)=\begin{bmatrix}\frac12&0&\frac13\\0&\frac14&0\\-\frac12&0&\frac13\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}$$ $f:\Bbb R^3\to \Bbb R^3$, can we still just test for $\|x\|=1$ and what do we choose for $x$? We need three terms I guess?

$\endgroup$
2
$\begingroup$

For your $3 \times 3$ problem: note that this is really just the $2 \times 2$ problem in disguise. In particular, we note that $$ \left\|\pmatrix{ \frac12&0&\frac13\\ 0&\frac14&0\\ -\frac12&0&\frac13 } \pmatrix{x_1\\x_2\\x_3}\right\|^2 = \left\|\pmatrix{ \frac12&\frac13\\ -\frac12&\frac13 }\pmatrix{x_1\\x_3}\right\|^2 + (x_2/4)^2 $$ From there, the technique you used last time applies.

I suspect that if they give you a $3 \times 3$ question on the exam, you can break it down like this.


Complete solution:

We see that $$ \left\|\pmatrix{ \frac12&\frac13\\ -\frac12&\frac13 }\pmatrix{x_1\\x_3}\right\|^2 = \left\| \pmatrix{(1/2) x_1 + (1/3)x_3\\ (-1/2)x_1 + (1/3)x_3} \right\|^2 =\\ [(1/2) x_1 + (1/3)x_3]^2 + [(-1/2)x_1 + (1/3)x_3]^2 =\\ [x_1^2/4 + x_1x_3/3 + x_3^2/9] + [x_1^2/4 - x_1x_3/3 + x_3^2/9] =\\ (1/2)x_1^2 + (2/9)x_3^2 \leq\\ (1/2)x_1^2 + (1/2)x_3^2=\\ (1/2)\|(x_1,x_3)\|^2 $$ So, we have $$ \left\|\pmatrix{ \frac12&0&\frac13\\ 0&\frac14&0\\ -\frac12&0&\frac13 } \pmatrix{x_1\\x_2\\x_3}\right\|^2 = \left\|\pmatrix{ \frac12&\frac13\\ -\frac12&\frac13 }\pmatrix{x_1\\x_3}\right\|^2 + (x_2/4)^2 \leq\\ (1/2)\|(x_1,x_3)\|^2 + (1/4)x_2^2 \leq\\ (1/2)\|(x_1,x_3)\|^2 + (1/2)x_2^2 =\\ (1/2)(x_1^2 + x_2^2 + x_3^2) =\\ (1/2)\|(x_1,x_2,x_3)\|^2 $$ We conclude that $f$ is a contraction with $k = \frac{1}{\sqrt{2}}$.

$\endgroup$
  • $\begingroup$ Oh wow, did you see that immediately, or you just realised it? Also what would be my smart choice for $x=(x_1,x_2,x_3)$ here? $\endgroup$ – Calculus Jun 17 '15 at 5:37
  • $\begingroup$ What you suspect is probably true, since the only two past exams I can view can be $\endgroup$ – Calculus Jun 17 '15 at 5:39
  • $\begingroup$ I noticed that besides the diagonal entry, all the entries in the second row and second column were $0$. $\endgroup$ – Omnomnomnom Jun 17 '15 at 5:39
  • $\begingroup$ I would set $x_1 = a\cos t, x_3= a\sin t$ with $a \in (0,1)$. Then you just need to remember that if $\|x\| = 1$, then $x_2^2 = 1-\|(x_1,x_3)\|^2$. $\endgroup$ – Omnomnomnom Jun 17 '15 at 5:41
  • $\begingroup$ The neat thing is that it is enough to show that the individual maps $$ x \mapsto \pmatrix{ \frac12&\frac13\\ -\frac12&\frac13 }x\\ x \mapsto x/4 $$ are contractions on $\Bbb R^2$ and $\Bbb R$, respectively. $\endgroup$ – Omnomnomnom Jun 17 '15 at 5:44
1
$\begingroup$

Yes, you can still use $\|x\|=1$. Yes, you will need 3 terms.

I would start by naively checking the norm of cos x, sin x, cos x

$\endgroup$
  • $\begingroup$ Why is the third term $\cos x$? I imagined the choice in the $\Bbb R^2$ case was because $x=\cos t + i\sin t=(\cos t,\sin t)$ and thus we were looking at $\Bbb C$, so I guessed that we would want spherical coordinates or something? $\endgroup$ – Calculus Jun 17 '15 at 5:13
  • $\begingroup$ @Calculus You could definitely use spherical coordinates, that is $$ (\sin s \cos t, \sin s \sin t, \cos s) $$ $\endgroup$ – Omnomnomnom Jun 17 '15 at 5:21
  • $\begingroup$ @Omnomnomnom Is this a reliable method in general though? It seems the hand-computations will be very tedious(especially in an exam!) side-note: my class taught us only how to do it with $2\times 2$ matrices, but all past exams(with no solution keys) have $3\times 3$ matrices!! $\endgroup$ – Calculus Jun 17 '15 at 5:24
  • $\begingroup$ @Calculus do you know about eigenvalues? $\endgroup$ – Omnomnomnom Jun 17 '15 at 5:25
  • $\begingroup$ @Omnomnomnom Yes, we can compute these by finding the characteristic equation, or if we are lucky(upper or lower triangular I believe) we can read them off(maybe something to do with being orthogonal here too?) $\endgroup$ – Calculus Jun 17 '15 at 5:25
1
$\begingroup$

More generally, suppose you have a $3\times 3$ matrix $A$ whose column vectors are orthogonal vectors $\mathbf u$, $\mathbf v$, and $\mathbf w$. Then I claim that $\|A\mathbf x\| \le k\|\mathbf x\|$ for $k=\max(\|\mathbf u\|,\|\mathbf v\|,\|\mathbf w\|)$. For note that $$A\mathbf x = x_1\mathbf u + x_2\mathbf v + x_3\mathbf w$$ and so \begin{align*} \|A\mathbf x\|^2 &= \|x_1\mathbf u + x_2\mathbf v + x_3\mathbf w\|^2 \\ &= \big(x_1\mathbf u + x_2\mathbf v + x_3\mathbf w\big)\cdot\big(x_1\mathbf u + x_2\mathbf v + x_3\mathbf w\big) \\ &= \|\mathbf u\|^2x_1^2 + \|\mathbf v\|^2x_2^2 + \|\mathbf w\|^2x_3^2 \\ &\le k^2(x_1^2+x_2^2+x_3^2) = k^2\|\mathbf x\|^2. \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.