2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ If A is deterministic $H(A) = 0$. Perhaps you meant $H(R)$ and $H(R | R^* A)$? $\endgroup$
    – Dinesh
    Mar 8, 2012 at 6:47
  • $\begingroup$ 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? $\endgroup$
    – Dilip Sarwate
    Mar 8, 2012 at 12:56
  • $\begingroup$ 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. $\endgroup$
    – user46
    Mar 8, 2012 at 19:24

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ humm, great insight - but excuse my ignorance of abstract algebra. Why exactly is matrix multiplication a group over invertible matrices? $\endgroup$
    – user996522
    Mar 9, 2012 at 1:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – poncho
    Mar 9, 2012 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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