Matrix optimization

4 次查看（过去 30 天）
John Martinez
John Martinez 2011-10-23
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.

请先登录，再回答此问题。

回答（5 个）

Walter Roberson
Walter Roberson 2011-10-23
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".
  1 个评论
Dr. Seis
Dr. Seis 2011-10-23
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.

请先登录，再进行评论。

John Martinez
John Martinez 2011-11-11
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.
  1 个评论
Walter Roberson
Walter Roberson 2011-11-11
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.

请先登录，再进行评论。

Vito
Vito 2011-11-11
Simplex algorithm?
Walter Roberson
Walter Roberson 2011-11-11
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.
  1 个评论
John Martinez
John Martinez 2011-11-11
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.

请先登录，再进行评论。

Vito
Vito 2011-11-12
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.
  1 个评论
Walter Roberson
Walter Roberson 2011-11-12
I have seen no evidence that this is a min-max question.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Operating on Diagonal Matrices 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by