1

I'm creating a code that that uses a matrix or matrices as a key. For example, given each string of $n$ letters, construct it into a vector using its position in the alphabet, and multiply it by an $n\times{n}$ matrix and the resulting vector is the encoded string.

Such a matrix would have to be non-singular, and it would have to be invariant on the set of vectors such that all of its components are positive integers and none of them are greater than $26$ (or how many letters there are in the particular character set). Is such a matrix (besides the identity matrix and permutation matrices) possible?

I suspect that it is impossible because the vector set is not a vector space, nor is it a subspace, but I don't know how to justify this.

If it is impossible to find such a matrix, can you provide a proof to demonstrate it?

rurouniwallace
  • 6,266
  • What is wrong with the identity matrix? – Lord Soth Jul 09 '13 at 20:19
  • 1
    @LordSoth: the identity matrix doesn't sound very encrypting. – Alex R. Jul 09 '13 at 20:21
  • @LordSoth Haha, well, that would be a pretty easy code to crack. – rurouniwallace Jul 09 '13 at 20:21
  • @Alex What is your definition of "encrypting?" – Lord Soth Jul 09 '13 at 20:22
  • 1
    You've also got a bunch of permutation matrices that I guess you will want to exclude as well – Cocopuffs Jul 09 '13 at 20:23
  • I guess what I am trying to say is that you need further constraints on the problem to avoid the trivial cases. I do not know what those constraints should be. – Lord Soth Jul 09 '13 at 20:23
  • @ZettaSuro: could you clarify the invariant part? Are you saying the matrix coefficients must be positive and within the range of the alphabet or is it just that the matrix maps strings to other strings, where a "string" is positive and within the alphabet range? – Alex R. Jul 09 '13 at 20:24
  • @Alex The second one, the matrix maps strings to other strings, where a string is positive and within the range of the alphabet. That is, provided that the pre-image is also positive and within the same range. – rurouniwallace Jul 09 '13 at 20:27
  • Bhs, brx dovr qhhg wr dyrlg shupxwdwlrqv dv Frfrsxiiv kdv vdlg. – Lord Soth Jul 09 '13 at 20:27
  • 1
    @ZettaSuro A thought: if you would take vectors with components $-12.5,-11.5,...,11.5,12.5$ instead of $1,...,26$, you would have some rotations and reflections that are nontrivial codes – Cocopuffs Jul 09 '13 at 20:36
  • @Cocopuffs ohh I see. Would all rotation and reflection matrices work? – rurouniwallace Jul 09 '13 at 20:43
  • @ZettaSuro No. Only those that map a cube onto itself. For example, combinations of 90 degree rotations, or reflections along the axes of symmetry – Cocopuffs Jul 09 '13 at 20:45

1 Answers1

0

Here is an alternate take. Suppose you are encoding bits instead of the alphabets (you can convert an alphabet to its bit representation so this is not restrictive). The probability that a random $n\times n$ binary matrix is invertible (even over $\mathbb{F}_2$) is positive (around $.29$) as $n\rightarrow\infty$ (see e.g. Probability that a random binary matrix is invertible?). So you have a lot of chance in finding such matrices. Also, according to what Will Orrick says on the same page, if you allow inversions over $\mathbb{R}$ the probability that your random $0$-$1$ matrix will be non-singular as $n\rightarrow\infty$ according to Tao and Vu.

Community
  • 1
Lord Soth
  • 7,750
  • 20
  • 37