Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Suppose I generate a random $m×m$ matrix $R$, where each of its elements belongs to $\mathbb Z_n$. I ensure that $R$ is invertible in $\mathbb Z_n^{m×m}$.

Now I take a non-random $m×m$ matrix $A$, where each of its elements belongs to $\mathbb Z_n$ and is not zero. I now multiply them both together to obtain $R·A$ and reduce $R·A$ modulo $n$.

My question is about its Shannon entropy: Is $H(A|R·A) = H(A)\ $?

share|improve this question
    
If A is deterministic $H(A) = 0$. Perhaps you meant $H(R)$ and $H(R | R^* A)$? –  Dinesh Mar 8 '12 at 6:47
    
Be careful when $n$ is not a prime because there can be unusual effects. For example, over $\mathbb Z_4$, the identity matrix $I$ is invertible, but $2I$ is not. Will this affect your entropy calculations? –  Dilip Sarwate Mar 8 '12 at 12:56
    
Moderator note: please don't cross post near identical questions; if your question isn't being answered you can always flag it for migration if you intend to ask the same one. It is acceptable to cross post questions where you're looking for differing points of view from different communities, but this way we just end up moving the Q to one site or the other :) In this case, don't worry about it too much, I've contacted the maths mods and we'll move/merge one of the Qs. –  Ninefingers Mar 8 '12 at 19:24
add comment

1 Answer

up vote 3 down vote accepted

Well, no, in general, it is not. Here's a simple example that demonstrates it is not:

Suppose that $m=2$, $n \ge 3$ and the matrix $A$ can take one of the following two values:

$\pmatrix{1&2\cr1&1}$ with probability $1/2$, and $\pmatrix{1&2\cr1&2}$ with probability $1/2$

Note that the first matrix is nonsingular (invertible), while the second is singular.

In this case, $H(A) = 1$

On the other hand, if we are given the value $R \cdot A$, this matrix is nonsingular if $A$ is the first value, and singular if $A$ is the second value. Hence, the value of $R \cdot A$ allows us to derive the value of $A$ with probability 1, and hence $H(A | R \cdot A) = 0$

If $A$ is constrained to be an invertible matrix, and $R$ can take on all invertible matrices with equal probability, then $H(A | R \cdot A) = H(A)$; this can be deduced from the fact that matrix multiplication is a group operation over invertible matrices.

share|improve this answer
    
humm, great insight - but excuse my ignorance of abstract algebra. Why exactly is matrix multiplication a group over invertible matrices? –  user996522 Mar 9 '12 at 1:53
1  
@user996522: It is a group because if we consider the set of all invertible matrices and consider the operation of matrix multiplication, it fulfills all the requirements of a group; it is closed (if A and B are invertible matrices, so is $A\cdot B$), it has associativity, it has an identity element, every element has an inverse). Why being a group is important is because, for any group operation $\oplus$, if R is a uniformly and independently distributed group element, then so is $R\oplus A$, in particular, $R\oplus A$ is independent of A. –  poncho Mar 9 '12 at 2:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.