# How do I row reduce a matrix mod 26 when it is singular mod 26?

Cryptography assignment question: matrix $A$ is $$A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 \end{array}\right)$$ (Hill Cipher key). Show that for a vector $x_1$, $x_1A=x_2A \mod 26$ for exactly $13$ $x_2$'s.

Progress so far: $\det(A)=13$ so $A$ is not invertible $\mod 26$. Re-write the problem as find $y$ such that $yA=0 \mod 26$. I thought I could find $y$ by finding the null space of $A$ $\mod 26$ but I don't know how to do that. It doesn't seem to be working.

• sorry forgot to mention that re-arranged it as (x1-x2)A=0 mod 26 and let (x1-x2)=y so there should be 13 different y vectors such that yA=0 mod 26 – Alan Jan 20 '14 at 22:42

So, $A=\pmatrix{1&0&0\\1&3&1\\0&2&5}$ and let $y=(y_1,y_2,y_3)$. Then we need to find the solutions of $yA=0$, i.e. $$\matrix{y_1+y_2 &=& 0 &&& (i) \\ 3y_2+2y_3 &=& 0 &&& (ii)\\ y_2+5y_3 &=& 0 &&& (iii) }$$ Now perform $(ii)\,-\,3\cdot(iii)$ to obtain $\ \ -13y_3=0 \quad\quad (iv)$.
Since all these are modulo $26$, any even $y_3\in\Bbb Z_{26}$ will be a solution of $(iv)$. (There are exactly $13$ even numbers modulo $26$.)
Then, $y_2$ can be uniquely determined by either $(iii)$ or $(ii)$, knowing the choice for $y_3$ and also, $y_2$ determines $y_1$ by $(i)$.