Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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. – user46 Mar 8 '12 at 19:24
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
@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

Your Answer


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.