# Testing for Linear Independence/rank mod m

I am working on cracking a hill cypher using modular linear algebra. Every example I have found online makes a big assumption that is not necessarily the case, and as I see it leaves a lot to be desired. It goes like this: You are working with an alphabet, say with 26 letters. You encode the cipher text as follows: c = Ap where c is a block of the cypher text, p is a corresponding block of the plaintext, and A is the encryption matrix. Skipping right to the point, lets say you have some general plaintext and cypher text, and you want to solve for A. Assuming that the key matrix is nxn, we can simply find n blocks of plaintext, and use them to form an nxn invertible matrix

P=[p_1|...|p_n]


and an associated (not necessarily invertible) matrix

C = [c_1|...|c_n]


So that we now have the system

C = AP


which we can of course solve by inverting P.

But here is the catch: we don't necessarily know that the columns of p are independent! In order to build a practical algorithm to solve this in the general case, we need to check each new block of plaintext p against the previous blocks to make sure it is linearly independent. Another way of saying this is that if we already have k blocks and we already have an nxk matrix

P* = [p_1|...|p_k]


we are looking to check if

P** = [p_1|...|p_k+1]


is full-rank. I have tried to figure out how to do this, but I can't seem to figure out a good algorithm to test it. I discovered by working out examples that you could test if two columns are independent exhaustively by simply multiplying one by succesively larger integers mod m. The result is a repeating pattern (the total number of possible vectors is finite), so this search will always be finite. But what is a less painful way of testing for linear independence/rank in modular matrix arithmetic?

Thanks in advance,

Paul

• Can we assume that $m$ is a prime number? – David Aug 1 '14 at 5:00
• unfortunately, no. In most examples I've seen m= 26. – Paul Aug 1 '14 at 5:02
• That will complicate things because it will mean that many of the usual "nice" properties of independent sets do not carry over. To give one example, $\{2,13\}$ is a linearly dependent spanning set for ${\Bbb Z}_{26}$ but it does not contain a linearly independent spanning set. – David Aug 1 '14 at 5:08
• yes, I agree, that does present a problem. If you are assuming the key is 2x2 and your first two letters of plaintext are "cn"={2,13}, you are basically stuck. And that is not the only way you may not be able to find linearly independent blocks. But the question of how to test still remains. – Paul Aug 1 '14 at 5:12
• I suppose a more appropriate way of doing this would be to find the reduced-row echelon form of the two vectors (using modular arithmetic), and check if any of the rows are all 0's. – Paul Aug 1 '14 at 6:22