# Is there a way to use a Hill cypher where the ciphering matrix is not square?

I've studied Hill's theory where, in order to cypher a vector $p$ of dimension $n\times 1$, we use a squared matrix $A$. We would multiply $Ap$ and get the $n\times 1$ vector $c$, we would then make a modulo $m$ operation, where $m$ is the number of characters we're using to encipher, so this vector $c$ has now values $\in \{1,2,...,m\}^n$. In order to get the original vector we would do the inverse process, multiply ${A^{-1}}c$ (we would have to make sure $A$ has an inverse matrix first), the result modulo $m$ is the original vector $p$. My question is: Is there a Hill cypher where $A$ may not be square? if so, how would it work? if not, is there a proof?

• I guess that in theory you only need the mapping $c\mapsto Ac$ to be injective. After all, there is no compelling need for all the vectors to be encrypted versions of a plaintext vector. – Jyrki Lahtonen Dec 1 '17 at 9:56

If $A$ is a $p \times q$-matrix then it transforms a $q \times 1$ vector to a $p \times 1$ vector (over $\mathbb{Z}_m$ in your case). This can only be bijective (invertible) iff $p=q$ because we map $\mathbb{Z}_m^q$ to $\mathbb{Z}_m^p$ and these sets have the same size iff $p=q$. So we need a square invertible matrix to get a valid encryption system with unique decryption.
• I agree, but what about using SVD or some other method in order to calculate the pseudo inverse matrix. ¿Would it be possible to somehow find an inverse modulo $m$ matrix using this kind of methods? – D. Tiburcio Dec 1 '17 at 17:15
• Hey @Henno Brandsma, I was thinking. That is true for a case where we want to map $\mathbb{Z}_{m}^{p}$ to $\mathbb{Z}_{m}^{q}$. But what about a case where we want to map $\mathbb{Z}_{a}^{p}$ to $\mathbb{Z}_{b}^{q}$, so that $ap = bq$. Would it be a way to make that work? – D. Tiburcio Dec 5 '17 at 18:26
• @D.Tiburcio you mean $a^p = b^q$ perhaps? – Henno Brandsma Dec 5 '17 at 18:33