# Shannon entropy calculation: is $H(A|R·A) = H(A)$?

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)\$?

• If A is deterministic $H(A) = 0$. Perhaps you meant $H(R)$ and $H(R | R^* A)$?
– Dinesh
Mar 8, 2012 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? Mar 8, 2012 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, 2012 at 19:24

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.

• humm, great insight - but excuse my ignorance of abstract algebra. Why exactly is matrix multiplication a group over invertible matrices? Mar 9, 2012 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. Mar 9, 2012 at 2:40