Copyright © University of Cambridge. All rights reserved.

'Fix Me or Crush Me' printed from http://nrich.maths.org/

Show menu


Doug writes:

For the first part, I took a general matrix $\begin{bmatrix} a&b&c\\ d&e&f\\ g&h&i\\ \end{bmatrix}$, and multiplied this with $\mathbf{F}$ to get $\begin{pmatrix} a+b\\ d+e\\ g+h\\ \end{pmatrix} \therefore$ a+b=1, d+e=1, g+h=0, and c,f,i are irrelevant. There are an infinite number of solutions to this.
Check the identity matrix is one, yes it is. The simplest non-identity is probably $\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&0\\ \end{bmatrix}$
And a complicated one is $\begin{bmatrix} m&1-m&j\\ n&1-n&k\\ p&-p&l\\ \end{bmatrix}$.

To crush $\mathbf{Z}$, I followed the same process. The simplest non-zero matrix is probably $\begin{bmatrix} 1&0&0\\ 0&0&0\\ 0&0&0\\ \end{bmatrix}$
And a complicated one is $\begin{bmatrix} j&m&-m\\ k&n&-n\\ l&p&-p\\ \end{bmatrix}$.

To find a matrix that achieves both, I just combined the equations found previously to the simultaneous set: a+b=1,d+e=1,g+h=0,b+c=0,e+f=0,h+i=0 $\therefore$ b=-c,e=-f,h=-i

$\therefore$ a-c=1,d-f=1,g-i=0

9 variables, 6 equations, but there is probably not just one unique solution.

In fact looking at these, we can quickly jump to $\begin{bmatrix} 1-j&j&-j\\ 1-k&k&-k\\ -l&l&-l\\ \end{bmatrix}$ which satisfies both sets, thus any matrix of this form will fix $\mathbf{F}$ and crush $\mathbf{Z}$.

The above matrix must be, and is, singular, i.e. the eigenvectors do not form an independent set. If the eigenvectors formed an independent set then there would be no vector that would be crushed by being transformed by the matrix.

For the next part, it seems that $\mathbf{F}$ and $\mathbf{Z}$ have been carefully chosen to have 1s and 0s to make simultaneous fixing & crushing possible.

I tried to prove this with the general matrix $\begin{bmatrix} a&b&c\\ d&e&f\\ g&h&i\\ \end{bmatrix}$ multiplied with a fixable general vector $\begin{pmatrix} j\\ k\\ l\\ \end{pmatrix}$ and a crushable general vector $\begin{pmatrix} m\\ n\\ p\\ \end{pmatrix}$
so we have 6 simultaneous equations:
aj+bk+cl=j
dj+ek+fl=k
gj+hk+il=l
am+bn+cp=0
dm+en+fp=0
gm+hn+ip=0

I proceeded to attempt to solve the simultaneous equations, but did not find a general argument to prove it either way.

Steve notes:

The first matrix fixes all vectors and crushes no vectors. So, clearly not all matrices crush vectors. I wonder if others fail to crush vectors?

Anyway, to determine more generally if a matrix $M$ crushes a vector $\mathbf{Z}$ we need to solve $M\mathbf{Z}= \mathbf{0}$. By putting this into components we get three simultaneous equations in $x, y, z$. For the second matrix, the equations I get are

$$x+2y+3z=0, 2x+3y+4z = 0, 3x+4y+5z=0$$

I can solve these by elimination to get the solution as

$$
2x=-y=2z
$$
This is a line of solutions - each vector can be written as $(a, -2a, a)$ for any number $a$.

To check, we can see that
$$
\begin{pmatrix} 1&2&3\\ 2&3&4\\ 3&4&5\\ \end{pmatrix}
\begin{pmatrix} a\\ -2a\\ a\\ \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ 0\\ \end{pmatrix}
$$

To determine if the same matrix fixes a vector, I need to solve
$$ \begin{pmatrix} 1&2&3\\ 2&3&4\\ 3&4&5\\ \end{pmatrix} \begin{pmatrix} x\\ y\\ z\\ \end{pmatrix} = \begin{pmatrix} x\\ y\\ z\\ \end{pmatrix} $$
This gives me equations
$$
2y+3z=0, 2x+2y+4z = 0, 3x+4y+4z=0
$$
I tried to solve these, but they proved to be inconsistent with no solution. So the second matrix does not fix any vector. So, there are clearly matrices which don't leave any vector fixed.

For the third matrix I saved some time by noticing that the second row is $(1, 1, 0)$. So, if this matrix is to crush any vector then that vector must be of the form $(a, -a, z)$.

Multiplying this vector by the matrix gives $(3a+z, 0, -3a-2z)$. This can't be set equal to zero for any choice of $a\neq 0$ and $z$, so the last matrix does not crush any vector.

What does it fix? The second row is again key. It implies that $x+y=y$ which implies that $x=0$. The other rows give equations $-2y+z=0$ and $y-2z=z$, which are inconsistent unless $y=z=0$. So, this matrix doesn't fix a vector either! I wasn't expecting that.

For the last part, note that if the vector $\mathbf{F}$ has all non-zero components $x, y$ and $z$ then it is always possible to construct a matrix such that $\mathbf{F}$ is fixed

$\begin{bmatrix} 1&a& -(x+ay)/z+x/z\\ 1&b& -(x+by)/z+y/z\\ 1&c&-(x+cy)/z+1\\ \end{bmatrix}$
It looks like variable choices $a, b, c$ will be sufficient to make it possible to crush any choice of vector $\mathbf{Z}$ which is not parallel to $\mathbf{F}$, but I'd better make sure.

Acting with this matrix on any other vector $(X, Y, Z)$ gives me

$$
X+aY+\left(\frac{x-(x+ay)}{z}\right)Z = X+bY+\left(\frac{y-(x+by)}{z}\right)Z =X+cY+\left(\frac{z-( x+cy)}{z}\right)Z=0
$$
I can rewrite this to make the factors of $a, b, c$ more clear as
$$
X+\left(\frac{x-x}{z}\right) Z+a\left(Y-\frac{y}{z}Z\right)=X+\left(\frac{y-x}{z}\right) Z+b\left(Y-\frac{y}{z}Z\right)=X+\left(\frac{z-x}{z}\right) Z+c\left(Y-\frac{y}{z}Z\right)
$$
Each choice $a, b, c$ premultiplies the same factor. So, if this factor is not zero I can choose $a, b, c$ so that $(X, Y, Z)$ is annihilated.

This leaves the case when the factor is zero, which occurs if and only if
$$
\frac{Y}{Z} = \frac{y}{z}
$$
Geometrically, this occurs when and only when the projections of the two vectors onto the $x=0$ plane are parallel.