Linear Algebra and Modular Math: We know that if a matrix A is n x n, then Ax = b (x and b are vectors) has a unique solution iff A is invertible. 2 questions:

1) If A is singular, then are there many solutions to Ax = b? Or are there no solutions?
2) If we are working with modular math and "=" is the congruence relation, then does the first statement I wrote still hold? Or should there be any changes in that statement?

Question

Linear Algebra and Modular Math: We know that if a matrix A is n x n, then Ax = b (x and b are vectors) has a unique solution iff A is invertible. 2 questions:

1) If A is singular, then are there many solutions to Ax = b? Or are there no solutions?
2) If we are working with modular math and "=" is the congruence relation, then does the first statement I wrote still hold? Or should there be any changes in that statement?

ganeshie8 · Answer

familiar with subspaces ?

anonymous · Answer

Vaguely.. I have taken linear algebra about 3 years ago and returning to it now since I'm taking cryptography haha.

ganeshie8 · Answer

the linear combinations of column vectors form column space

when A is singular, there will be many points(b's) that lie outside the column space, so you won't be able to reach all points by taking the combinations of column vectors

ganeshie8 · Answer

Consider below system :

x + y = 2
2x+2y = 4

A :
1 1
2 2

b:
2
4

ganeshie8 · Answer

above system has a solution because the vector $\large \binom{2}{4}$ is in column space of A

ganeshie8 · Answer

For the same matrix, A, there will NOT be a solution for a random vector like, $\large \binom{1}{3}$ :  
$$\large   \begin{pmatrix} 1&1\2&2 \end{pmatrix}\begin{pmatrix} x\y\end{pmatrix} = \begin{pmatrix} 1\3\end{pmatrix}$$

ganeshie8 · Answer

To answer your specific question :
1) If A is singular, then are there many solutions to Ax = b? Or are there no solutions?


Ax=b has infinitely many solutions when `b` is in column space of A

Ax=b has 0 solutions otherwise

anonymous · Answer

Ah, thank you for that, I could see why from your explanations. Thank you!

ganeshie8 · Answer

Could you shed some more light on what you mean by $\large Ax \equiv b$ ?

anonymous · Answer

So the second question.. what would change from all of these if Ax=b is under mod n?

ganeshie8 · Answer

$\large Ax\equiv  b\pmod n$

? 

what exactly is this ?

anonymous · Answer

Oh, I mean for example, in regular (sorry for the lack of a better term) math, a matrix A is invertible if the determinant is not 0, but in modular math, an added condition is that A and n (if we're working in mod n) must be relatively prime. I was wondering if there's also a similar added condition in this context.

ganeshie8 · Answer

Hmm... let me try and see if I get what you're doing.

when $a$ is a scalar,
$\large  ax\equiv  1\mod n$ has a solution, right ?

ganeshie8 · Answer

how do you define congruence in context of matrix ? do you take mod for each element ?

anonymous · Answer

Hmm maybe I should not have said congruence.. maybe that was careless writing on my part. I was really just wondering what would happen when the numbers in the matrix and vectors in Ax=b are allowed to have equivalent numbers mod n.

anonymous · Answer

anyway, thank you very much! I'm about to eat dinner for now, so I'll be off the computer for a while

ganeshie8 · Answer

$$\large  \begin{pmatrix}  a_1&b_1\a_2&b_2\end{pmatrix} \begin{pmatrix}  x\y\end{pmatrix}= \begin{pmatrix}  c_1\c_2\end{pmatrix}   $$

Versus

$$\large  \begin{pmatrix}  a_1\mod n&b_1 \mod n\a_2\mod n&b_2\mod n\end{pmatrix} \begin{pmatrix}  x\y\end{pmatrix}= \begin{pmatrix}  c_1\mod n\c_2\mod n\end{pmatrix}   $$

ganeshie8 · Answer

what good is that hmm

anonymous · Answer

Yes. Would anything that we've said so far change if that's the case?

anonymous · Answer

It's okay haha. Anyway I'm really going now. These are just curious questions that I've thought of to solve the problems in my homework

ganeshie8 · Answer

$\large   (a_ix+b_iy) \mod n  =  c_i  \mod n$

ganeshie8 · Answer

I don't see any problem with the system as you're taking mod both sides

anonymous · Answer

Essentially the whole point of me to ask these questions is to figure out if two plaintexts can map to the same ciphertext in a Hill Cipher

ganeshie8 · Answer

Ahh I see :) i have no clue but it looks interesting 

It seems, to encrypt vector x, you're taking 
$\large   Ax \pmod{26}$

ganeshie8 · Answer

Since $A$ is invertible, there will be one-to-one relationship between `x` and `Ax`

we need to think a bit more on what happens after taking mod 26

anonymous · Answer

@ganeshie8  Yes! That's exactly what I'm getting at. Sorry for beating around the bush so much.

ganeshie8 · Answer

$$\large Ax \equiv b \pmod n  \implies x = A^{-1}b \pmod{n}$$

ganeshie8 · Answer

for $\large A^{-1}$ to exist,  $\large  \det(A)$ must not be $0$
also the multiplicative inverse of $\large \det(A)$ must exist in $\large \mod n$

ganeshie8 · Answer

I still don't see why/how you think there is a possibility for two plaintexts to map to same cipher text

anonymous · Answer

If the user of the cipher decides to use a matrix key that is singular.. then for certain ciphertexts, there could be two plaintexts that map to it, no? just like how Ax=b has infinitely many solutions when b is in the column space of A?