# Matrix optimization

조회 수: 2 (최근 30일)
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 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이전 댓글 -1개 표시이전 댓글 -1개 숨기기
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 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이전 댓글 -1개 표시이전 댓글 -1개 숨기기
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 2011년 11월 11일
Simplex algorithm?
##### 댓글 수: 0이전 댓글 -2개 표시이전 댓글 -2개 숨기기

댓글을 달려면 로그인하십시오.

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이전 댓글 -1개 표시이전 댓글 -1개 숨기기
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 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이전 댓글 -1개 표시이전 댓글 -1개 숨기기
Walter Roberson 2011년 11월 12일
I have seen no evidence that this is a min-max question.

댓글을 달려면 로그인하십시오.

### 카테고리

Help CenterFile 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