Can you solve this? Yes, sometimes, and there is no need for random permutations of the matrix. In fact, that is a poor solution, since there is indeed a simple solution that has no need for random swaps. But first...
A serious flaw in your problem is there are some matrices (easy to construct) that can NEVER be made diagonally dominant using simply row exchanges.
I'll paste in the important wording here:
"a square matrix is said to be diagonally dominant if, for every row of the matrix, the magnitude of the diagonal entry in a row is larger than or equal to the sum of the magnitudes of all the other (non-diagonal) entries in that row. "
So it is clearly true that there can easily be rows that can never satisfy that requirement. For example, consider the row vector:
Row = [10 10 1 1 1 1 10];
Suppose we made this to be the first row of the matrix? Well, then we must have 10 (the first element) being larger than the sum of the magnitudes of the other elements.
Likewise, if we made it the second row, or the last row, then we still have the same problem.
Row = [10 10 1 1 1 1 10];
sum(abs(Row(2:end)))
ans =
24
As long as that row is in the matrix, there is NO possible re-ordering that will make the matrix diagonally dominant. It simply cannot happen, because no matter which row you swap it to, it will always fail the requirement.
In fact, I could have made it even simpler. How about this row vector?
Where would you swap that row to, such that the matrix will now be diagonally dominant? You cannot ever find a solution, even disregarding all other rows of the matrix. If your matrix has such a row, then you can never succeed.
Even more interesting though, is we can show that any row can only ever live in ONE position, IF the matrix is to be strictly diagonally dominant. That is because we need only find the largest element in any row in abolute magnitude. The position of that element tell you which row it needs to be in. Case closed.
Now, having said that, why did I say that it is possible to find a non-random solution SOME of the time? In fact, it is simple to derive such an algorithm. Consder ANY row. Find the maximum absolute value of that element. If that value exceeds the absolute sum of the remainder of the row elements then that row is POTENTIALLY a candidate for being in a diagonally dominant matrix.
Is there a problem here? Well yes. suppose that two rows must both be row 1? Consider these two rows:
Row1 = [10,rand(1,5)];
Row2 = [11,rand(1,5)];
There is only one position for either of those rows to live in, IF the corresponding matrix will be DD. If your matrix has both of those rows, then you are stuck, up a creek without a paddle. There would be no solution.
A = randi(5,[5,5]) + eye(5)*100;
A = A(randperm(5),:)
A =
4 2 1 101 1
5 104 3 4 1
105 5 2 2 3
5 4 105 4 4
2 4 4 1 101
If we consider the matrix A, as I created it there is CLEARLY a permutation that will yield a diagonally dominant matrix as a solution. What is it? All we need is ONE simple call to the function max do most of the work.
[maxrow,maxind] = max(abs(A),[],2)
maxrow =
101
104
105
105
101
maxind =
4
2
1
3
5
Now, CAN the matrix be made to be diagonally dominant? there are two tests necessary. First, we need for this to be true:
all(maxrow > (sum(abs(A),2) - maxrow))
ans =
logical
1
Think about why it is necessary. In order for the matrix to be STRICTLY diagonally dominant, we need that strict inequality too. A simpler >= will not suffice.
Next, we need for the vector maxind to be a permutation of the numbers 1:5. We might write it like this:
isequal(sort(maxind),(1:numel(maxind))')
ans =
logical
1
There are other ways I could have written that test, but it is sufficient and necessary.
Regardless, now what is the solution? SIMPLE!
A(maxind,:) = A
A =
105 5 2 2 3
5 104 3 4 1
5 4 105 4 4
4 2 1 101 1
2 4 4 1 101
As such, the code to perform what you asked for is both trivial to write and fast to execute.
function A = makeDD(A)
[n,m] = size(A);
if n~= m
error('A is not square')
end
[maxrow,maxind] = max(abs(A),[],2);
if all(maxrow > (sum(abs(A),2) - maxrow)) && isequal(sort(maxind),(1:numel(maxind))')
A(maxind,:) = A;
else
disp('Sorry, but this matrix can never be made to be diagonally dominant')
A = [];
end
end
Let me test it now.
A = magic(3)
A =
8 1 6
3 5 7
4 9 2
makeDD(magic(3))
Sorry, but this matrix can never be made to be diagonally dominant
ans =
[]
As you can see, even though A has distinct maximal elements which are larger than the rest in that row, AND they fall in distinct columns, it still fails the other test, that for the second row of A, we must have had 7 > (3+5).
Change A just a tiny bit by changing one element, we can succeed however.
A(2,3) = 12
A =
8 1 6
3 5 12
4 9 2
makeDD(A)
ans =
8 1 6
4 9 2
3 5 12
In all of this you need to see the solution is always trivial to find, IF one exists, and that it requires no random permutations, Finally, see that the solution, if it DOES exist, is unique.
As I said, the code I wrote is blazingly fast, even for huge matrices. Consider this case for a 100x100 row-randomized matrix. Again, I'll construct it where the matrix is known to have a solution.
A = randi(5,[100,100]) + eye(100)*1000;
A = A(randperm(100),:);
tic,Ahat = makeDD(A);toc
Elapsed time is 0.002210 seconds.
So 0.002 seconds to solve a problem that if we used random permutations would take the lifetime of the universe to solve, even using a computer the size of the entire universe.
factorial(100)
ans =
9.33262154439441e+157
