Matrix optimization

I know the sum of each row and sum of each column and that the Trace(A) = 0 (and a[i,j] = 0 if i=j) of a 9x9 matrix and I was wondering if Matlab can find the most efficient matrix that meets this criteria.

Answer 1

[Walter Roberson]

No. MATLAB has no idea what makes one matrix more "efficient" than another.

For that matter, I have no idea what it would mean for something to be "the most efficient matrix that meets this criteria".

[Dr. Seis]

Yeah, not sure. Maybe he just means a unique solution. However, if so, it should be said that there are a ton of solutions to a blank 9x9 sudoku game (even with the extra diagonal constraint) and there are only 9 different numbers that each element can be, too! There can't be any fewer than an infinite number of solutions when you open up the rest of the catalog of just the natural (not to mention rational or real) numbers for the conditions set above.

Answer 2

[John Martinez]

I realize that my system is underdetermined but I know what the matrix is. A large # of the entries are zero (almost 40%)and was wondering if this qualifies as a sparse matrix. I know that A*x=b1 and that transpose(A)*x=b2, where x=(1 1 1 1 1 1 1 1 1)^T. So b1 and b2 are just the sums of the rows and columns, respectively. What I want is to assume I don't know Matrix A and given that it is sparse, can matlab generate a unique solution.

[Walter Roberson]

A matrix is sparse if and only if it was constructed using the sparse matrix class. Whether using a sparse matrix to represent any particular matrix is _efficient_ is a different question. Knowing that a matrix is sparse does not add or remove any solutions.

Answer 3

[Vito]

Simplex algorithm?

Answer 4

[Walter Roberson]

If you have an n x n matrix whose diagonals are known to be 0, but whose exact contents at any other location are at best known probabilistically (e.g., 40% zeros), then you have n * n total locations minus the n known zeros to give n * (n-1) unknown variables.

If you know the row and column sums, then you know n totals along the rows, and n totals along the columns for a total of 2*n totals.

You thus have 2*n equations (of totals) in n * (n-1) unknowns.

The only non-zero order for which that can be solved uniquely is the 3 x 3 matrix.

For the 9 x 9 matrix, you have 18 equations in 72 unknowns.

Even if you know the exact location of the 40% zeros, that would give values to ceil(2/5 * 81) - 9 (diagonals already known) = 24 of the 72 unknowns. That would take you to 18 equations in 48 unknowns, which is still far far too underdetermined for a unique solution.

Your matrix would have to be 7/9'ths zeros (all in known locations) to get down to 18 unknowns to allow you to get a unique solution.

[John Martinez]

Thanks Walter, that makes sense. I forgot to mention that the matrix entries have to be non-negative integers, not sure if that changes anything.

Answer 5

[Vito]

John Martinez.

At you the typical task of optimization which has set of decisions. For you the unique decision will be either max or min? Simplex the method allows to sort out all these decisions and is supported Matlab.

Look at its theoretical description.

Walter Roberson.

All is true. But. Task essence to consider some convex set restricted from below (values should be more zero) and to find among set of decisions optimal (min or max).

The most suitable algorithm - Simplex (though it is formal it and isn't proved). Basis - a method of the Gauss.

[Walter Roberson]

I have seen no evidence that this is a min-max question.