We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings.

For a binary square matrix, it is not sufficient to just convert the matrix into binary string and measure its information content or its randomness since naive unraveling of the binary matrix into binary string would lose the adjacency information in each row and in each column.

My question: What are the analogous notions for measuring the information content and randomness of binary square matrix?


You claim that unraveling the (square) matrix into a vector loses some information. However, the transformation is bijective - given the $n^2$ vector, you can easily reconstruct the $n\times n$ matrix. Information theory is oblivious to representation. If you have some random variable $X$ and some bijection defined on its domain $f$ then $H(X) = H(f(X))$. So classical information theory covers the case of matrices.

| cite | improve this answer | |
  • $\begingroup$ Thanks Yuval. I guess you are assuming that $f$ is known or it is a fixed function $f$. Given $n^2$ string, there are many possible matrices depending on the unraveling method (scan order). Don't you agree? $\endgroup$ – Mohammad Al-Turkistany Apr 27 '13 at 16:23
  • 2
    $\begingroup$ It doesn't matter. When calculating the entropy of a random matrix, you use the formula $-\sum_x \Pr[A = x] \log \Pr[A = x]$. There is no mention here of any kind of representation. If it helps in calculating the entropy, you can choose whatever representation you wish, but it's only for convenience. And it's you who gets to choose. $\endgroup$ – Yuval Filmus Apr 27 '13 at 16:49
  • $\begingroup$ I still argue that a $n^2$ binary string with H-adjacency and V-adjacency defined by some function holds more information than just plain $n^2$ binary string. I hope my motivation is clear now. $\endgroup$ – Mohammad Al-Turkistany Apr 27 '13 at 18:35
  • 1
    $\begingroup$ No it doesn't. The entire point of information theory is to define intrinsic measures of information that don't rely on what you think is important in your data. $\endgroup$ – Yuval Filmus Apr 27 '13 at 18:39
  • 1
    $\begingroup$ In what sense would they have different information content? You have to spell that out. In the standard sense, the corresponding vectors would have exactly the same entropy. $\endgroup$ – Yuval Filmus Apr 28 '13 at 13:54

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.