Gaussian exception - linear equation matrices, algorithm

Question

Suppose we have a simple matrix 3rows x 7cols. The matrix includes only zeros (0) and (1), such as:

1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 

Senario: If we know the sum of the non-zeros in each row,

(in the first line 4, in the second line - 2, in the third line - 3.) (blue line)

Additionally, if we know the sum of each col (1, 0, 3, 2, 2, 1, 0) (green line)

also if we know the sum of each diagonal from upper left to lower right (1,0,1,2,3,0,1,1,0) (red lines) counterclockwise

and finally, we know the sum of each diagonal from bottom left to top right (0,0,2,1,3,2,1,0,0) (yellow lines)

My question is: With these values ​​as input (and a 3x7 matrix length),

 4, 2, 3 1, 0, 3, 2, 2, 1, 0 1, 0, 1, 2, 3, 0, 1, 1, 0 0, 0, 2, 1, 3, 2, 1, 0, 0 

How can we draw the first matrix? After many thoughts, I came to the conclusion that this is a linear system of equations with 3x7 unknown values ​​and some equations. Right?

How can I make an algorithm in C or something else to solve these equations? Should I use a method similar to the Gausian equation?

Any help would be greatly appreciated!

Answer 1

For an array of 10x15 units and zeros, you would try to find 150 unknowns and have equations 10 + 15 + 2 * (10 + 15-1) = 73 if you ignore that the values ​​are limited to one or zero. Obviously, you cannot create a linear system on this basis that has a unique solution.

Is this restriction enough to give a unique solution?

For a 4x4 matrix with the following sums, there are two solutions:

 - 1 1 1 1 | 1 1 1 1 \ 0 1 1 0 1 1 0 / 0 1 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 

Therefore, I did not expect that there will be a unique solution for large matrices - the same symmetry will exist in many places:

 - 1 1 0 0 1 1 | 1 1 0 0 1 1 \ 0 1 0 0 1 0 1 0 0 1 0 / 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 

Answer 2

Start with the first column. You know the upper and lower values ​​(from the first values ​​of the red and yellow lists). Subtract the sum of these two from the first in the green list, and now you also get the average.

Now just work right.

Subtract the average value of the first column from the next value in the red list, and you get the second value of the upper column. Subtract the same average from the next value in the yellow list, and you get the second lower value of the column. Subtract the sum of these two from the next value in the green list, and now you have the average for the second column.

et cetera

If you are going to code this, you can see that the first two columns are a special case, and this will make the code ugly. I would suggest using two “ghost” columns of all zeros on the left so you can use one method to determine the upper, lower, and middle values ​​for each column.

It is also easy to generalize. You just need to use the (#rows) -1 ghost columns.

Enjoy.

Answer 3

You can use the expansion of singular values ​​to compute a nonzero least squares method for a system of linear homogeneous (and heterogeneous) equations in matrix form.

Short review:

http://campar.in.tum.de/twiki/pub/Chair/TeachingWs05ComputerVision/3DCV_svd_000.pdf

You must first write out your systems as a matrix equation in the form Ax = b, where x is 21 unknown as a column vector, and A is a 28 x 21 matrix that forms a linear system when multiplied. You essentially need to calculate the matrix A of linear equations, calculate the decomposition of the singular values ​​of A, and paste the results into the equation, as shown in equation 9.17

There are many libraries that will calculate SVD for you in C, so you just need to formulate the matrix and perform the calculations in 9.17. The hardest part is probably understanding how it all works; relatively small code is required with the SVD library function.

To begin work on the formation of the equation of linear systems, consider the simple case of 3 x 3.

Suppose our system is a matrix of the form

 1 0 1 0 1 0 1 0 1 

We would have the following inputs to the linear system:

 2 1 2 (sum of rows - row) 2 1 2 (sum of colums - col) 1 0 3 0 1 (sum of first diagonal sets - t2b) 1 0 3 0 1 (sum of second diagonal sets - b2t) 

then now we will create a matrix for the linear system

  A a1 a2 a3 b1 b2 b3 c1 c2 c3 unknowns (x) = result (b) sum of row 1 [ 1 1 1 0 0 0 0 0 0 ] [a1] [2] sum of row 2 [ 0 0 0 1 1 1 0 0 0 ] [a2] [1] sum of row 3 [ 0 0 0 0 0 0 1 1 1 ] [a3] [2] sum of col 1 [ 1 0 0 1 0 0 1 0 0 ] [b1] [2] sum of col 2 [ 0 1 0 0 1 0 0 1 0 ] [b2] [1] sum of col 3 [ 0 0 1 0 0 1 0 0 1 ] [b3] [2] sum of t2b 1 [ 1 0 0 0 0 0 0 0 0 ] [c1] [1] sum of t2b 2 [ 0 1 0 1 0 0 0 0 0 ] [c2] [0] sum or t2b 3 [ 0 0 1 0 1 0 1 0 0 ] [c3] [3] sum of t2b 4 [ 0 0 0 0 0 1 0 1 0 ] [0] sum of t2b 5 [ 0 0 0 0 0 0 0 0 1 ] [1] sum of b2t 1 [ 0 0 0 0 0 0 1 0 0 ] [1] sum of b2t 2 [ 0 0 0 1 0 0 0 1 0 ] [0] sum of b2t 3 [ 1 0 0 0 1 0 0 0 1 ] [3] sum of b2t 4 [ 0 1 0 0 0 1 0 0 0 ] [0] sum of b2t 5 [ 0 0 1 0 0 0 0 0 0 ] [1] 

When you multiply Ax, you see that you get a linear system of equations. For example, if you multiply the first row by unkown columns, you get

 a1 + a2 + a3 = 2 

All you have to do is put 1 in any of the columns that appear in the equation and 0 in another place.

Now you need to calculate SVD A and connect the result to equation 9.17 to calculate the unknowns.

I recommend SVD because it can be calculated efficiently. If you prefer, you can increase the matrix A with the result vector b (A | b) and put A in the reduced form of the line level to get the result.

Answer 4

How about this as another option

 Count the amount of unknown squares each sum passes through While there are unsolved cells Solve all the cells which are passed through by a sum with only one unknown square Cells are solved by simply subtracting off all the known cells from the sum Update the amount of unknown squares each sum passes through 

There are no boundary cases, but it is very similar to the previous answer. This would first resolve all corners, then those that are adjacent to the corners, then these one step more interior from it, etc.

Edit: also zero out any paths that have a sum of zero that should solve any solvable ones (I think)