November 2, 2021

Open Jupyter notebook in Colab

Linear transformation for simple encryption and decryption is an interesting and reasonably simple example and application of invertible matrices. An invertible linear transformation could be used to scramble information encoded in a column vector or matrix composed of column vectors, and the inverse transformation could be used to un-scramble it.

Suppose the standard matrix for a linear transformation $\mathbf{T}(x)$ is an $m\times m$ “scrambled” identity matrix whose columns have been re-arranged. Each of the $m$ columns is an $m\times 1$ vector with a pivot position, but not necessarily in echelon form. For example if $\mathbf{A}$ is $3\times 3$ with columns $\mathbf{e_a}, \mathbf{e_b}, \mathbf{e_c}$ where $\mathbf{e_i}$ is a sparse vector with a value of 1 in the $i^{th}$ entry, $a, b, c \in {1,2,3}$, and $a≠b≠c$, and is multiplied on the right by a $3\times 1$ column vector $\mathbf{x}$ whose entries are $x_1$, $x_2$, $x_3$, the result will be a $3\times 1$ vector, $\mathbf{b}$, whose entries correspond in order of a, b, c such that $b_1=x_a$, $b_2=x_b$, $b_3=x_c$. The layout, or column order of $\mathbf{A}$ determines the row/entry output order of the resulting vector. Since $\mathbf{A}$ is invertible, multiplying $\mathbf{b}$ on the left by $\mathbf{A^{-1}}$ will return the original input vector $\mathbf{x}$.

For example if

$$ \mathbf{A}=\begin{bmatrix}0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\end{bmatrix} \quad and \quad \mathbf{x}=\begin{bmatrix}1 \\ 2 \\ 3\end{bmatrix} $$

then $\mathbf{A}\mathbf{x}$ is equal to

$$ \mathbf{A}\mathbf{x}=\begin{bmatrix}0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\end{bmatrix} \begin{bmatrix}1 \\ 2 \\ 3\end{bmatrix} = \begin{bmatrix}3 \\ 2 \\ 1\end{bmatrix} =\mathbf{b} $$

The inverse of $\mathbf{A}$ is given by:

$$ \mathbf{A^{-1}}=\begin{bmatrix}0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\end{bmatrix} $$

and

$$ \mathbf{A^{-1}}\mathbf{b}=\begin{bmatrix}0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\end{bmatrix} \begin{bmatrix}3 \\ 2 \\ 1\end{bmatrix} = \begin{bmatrix}1 \\ 2 \\ 3\end{bmatrix} =\mathbf{x} $$

The next step along this exploration was to ask what information could be encoded in a column vector, such that the transformed (re-arranged) vector would contain information that could be decoded into the same information system. I wanted to create an example with text so I looked up ASCII characters (various plaintext characters) and saw that there were 128 total. However, you could squeeze all capital letters, the 10 digits, and the more important symbols into 64 characters. I tinkered with binary encoding and settled on a system where the $i^{th}$ digit, $d_i ∈ {0,1}$, would represent value of $d_i \times 2(i-1)$. The total value would be equal to the sum of the values of 1 through $n$ digits:

$$ \sum_{i=1}^{n} d_i\cdot2^{i-1},\ d_i\in{0,1} $$

To encode 64 ($2^6$) different characters (0 through 63 in normal base-10 numbering), you need 6 digits. For example, the digits $(d_6 d_5 d_4 d_3 d_2 d_1)$ ‘000000’ is equal to 0, ‘111111’ is equal to 63, and ‘001101’ is equal to 13 $(1\times2(4−1)+1\times2(3−1)+1\times2(1−1))$. Each of the 64 characters is mapped to a base-10 number 0-63 (mapping included further below), which is then encoded in this system. These values can then be easily transferred to a $6×1$ column vector $\mathbf{x}$ whose entries $x1…x6$ are equal to $d1…d6$. A $6×n$ matrix, $\mathbf{S}$, can also be assembled from multiple encoded character column vectors.

For example the string ‘My name is Sam’ corresponds to base-10 numbers {46, 58, 1, 47, 34, 46, 38, 1, 42, 52, 1, 52, 34, 46}, which can then be encoded in the $6\times 14$ matrix $\mathbf{S}$:

$$ \mathbf{S^T}=\begin{bmatrix} 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 \\ \end{bmatrix} $$

Suppose $\mathbf{A}$ is equal to the $6\times 6$ matrix composed of columns $e_6, e_5, e_4, e_3, e_2, e_1$:

$$ \mathbf{A}=\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} $$

Multiplying $\mathbf{S}$ on the left by $\mathbf{A}$ will reverse the order of entries in each column of $\mathbf{S}$.