2
$\begingroup$

Introduction:

Define a "Bit Map" to be a matrix whose entries can only be $0$ or $1$. Then numbers above and beside each column and row indicates how many entries are "filled" with a one.

For example consider,

$$ \begin{array}{c|lcr} & 2 & 2 & 2 \\ \hline 2 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 3 & 1 & 1 & 1 \end{array} $$

The $3$ by $3$ matrix depicted above, consists of zeros and ones, and the numbers outside tell you how many ones are in each row/column.

The real problem is finding the solution when all that is given is the above numbers, the number of ones in each column and row, and none of the binary entries are given. Keep in mind, that the inverse solution is NOT unique. Although, there are some interesting symmetries.

Conjecture:

The method to solve for the binary entries given the number of ones in each row and column is layed out as follows. Each entry is assigned a value according to $$g(r,c,i)={{x_c \cdot y_r} \over {o_c \cdot o_r}}$$

where

$r$ is the row number

$c$ is the column number

$i$ is the iteration number which starts at 0

$g(r,c,i)$ is the entry in the $r$th row & the $c$th column at iteration $i$

$x_c(0)$ is the number of entries in the column that can be filled.

$x_c(i)$ is the number of entries in the column that can still be filled.

$y_r(0)$ is the number of entries in the row that can be filled.

$y_r(i)$ is the number of entries in the row that can be filled.

$o_r$ & $o_c$ represent the number of rows and columns in the matrix.

To create the solution to this inverse problem, these steps must be followed. The iteration starts at $i=1$ and all entries in the matrix are undetermined.

(1) Find the maximum $g(r,c,i)$ in the matrix and denote it by $M_i$ fill it's entry to $1$. Denote the row and column it was found in by $m_r$ and $m_c$. Since there will be more than one maximum, pick one at random to proceed.

(2) Take $m_r$ and $m_c$ to use in the next equations.

$$o_r(i+1)=o_r(i)-1$$ $$o_c(i+1)=o_c(i)-1$$ $$x_c(i+1)=x_r(i)-1$$ $$y_r(i+1)=y_r(i)-1$$

(3)

If $o_r(i+1)$ or $o_c(i+1)$ is zero, all g(r,c) must be recalculated. If not, then calculate $g(m_r,m_c,i+1)$ and for the other entries set $g(r,c,i+1)=g(r,c,i)$

(4) If $\sum_c x_c(i)$ or $\sum_r y_r(i)$ equals $\sum_c x_c$ or $\sum_r y_r$ then we are done, fill the other entries with $0$. Otherwise, The iteration is now at $i+1$ move on to $i+2$

Interpretation and Proof

How does one interpret $g$? And how does on prove that this method indeed provides a solution to the problem?

I've noticed that the sum of the $g$ is of the form.... $$\sum g = {{(\sum_c x_c) \cdot (\sum_r y_r)} \over {o_c \cdot o_r}}$$ which may or may not have an interpretation.

As far as the proof is concerned. There is some rough multiplications of probability going on here, which may indicate some kind of convolution of discrete measures perhaps?

I know this is a long post, so there may be typographical errors, feel free to point them out. Also feel free to provide an example of the algorithm failing.

$\endgroup$
  • $\begingroup$ For your example $3\times3$ array, what about the array $$\left(\begin{array}{ccc} 1 & 1 & 0\\ 0 & 0 & 1\\ 1 & 1 & 1\end{array}\right)?$$ I think it has the same number of ones in the rows and columns as yours $\endgroup$ – Lythia Jun 29 '15 at 16:04
  • $\begingroup$ @Lythia Yes, I've proved that if this method works, there will always be multiple solutions to the inverse problem, as long as there are multiple maximum $g$. $\endgroup$ – Zach466920 Jun 29 '15 at 16:12
  • $\begingroup$ Great. Then you should mention this (the inverse is not unique) in the introduction. $\endgroup$ – Lythia Jun 29 '15 at 16:15
  • $\begingroup$ @Lythia sorry, I didn't think to include that. It's there now though :) $\endgroup$ – Zach466920 Jun 29 '15 at 16:17
1
$\begingroup$

Your problem reminds me of an error detection and correction problem:

A $n^2$ bits message protected by $2n$ bits of redundancy.

The problem is that you can not reconstruct arbitrary messages with that much redundancy, I believe.

$\endgroup$
  • $\begingroup$ That is true, there are $n^2$ entries and only ${{n^2+n} \over 2}$ different values $g$ can take. So I can't get unique solutions as $n^2 \gt n$. Still, do you think the algorithm delivers at least a solution, even if it's not unique? $\endgroup$ – Zach466920 Jun 29 '15 at 16:41
  • $\begingroup$ Lets assume I would understand the description so much that I would be able to implement it. Then it would be easy to feed it with all $2^9=512$ matrices and I would expect it to reconstruct the matrix from the redundancy in about $2^6=64$ cases at most. $\endgroup$ – mvw Jun 29 '15 at 16:59
  • $\begingroup$ Yes, but this wasn't about finding the original matrix, as there are indeed multiple matrices. Have you ever heard of Pi-Cross? It's a toy model of that... $\endgroup$ – Zach466920 Jun 29 '15 at 17:14
  • $\begingroup$ Interesting. The codes there look a bit more complex. $\endgroup$ – mvw Jun 29 '15 at 17:18

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.