577 views (last 30 days)

Hello everyone ! Hope everyone is safe and healthy in light of the recent developments.

I'm trying to create a matlab code that takes a given matrix, firstly tests if the matrix is diagonally-dominant, if it is not, then the matrix rows are randomly swapped and the test is carried out again until the matrix is diagonally dominant. I know that this is definitaly not the most efficient way to convert a matrix to be diagonally dominant, however it is the best approach i could come up with the MATLAB knowledge that i know.

This is a script that tests if the matrix is diagonally dominant;

function [isdom] = IsDiagDom( A )

isdom = true;

for r = 1:size(A,1)

rowdom = 2 * abs(A(r,r)) > sum(abs(A(r,:)));

isdom = isdom && rowdom;

end

if isdom == 0

disp (['Matrix A is not diagonally-dominant']);

elseif isdom == 1

disp (['Matrix A is diagonally-dominant']);

end

end

And this is the script that im trying to make work that if the matrix is not diagonally dominat, the rows are randomly swapped and tested till it becomes diagonally dominant;

When i try to run the script, it says ' Invalid expression. When calling a function or indexing a variable, use parentheses. Otherwise, check

for mismatched delimiters. ' in the 'for ...' line

function [ A ] = DiagDom

A = [ 4 -28 -7 1; 4 -1 10 -1; -4 0 -3 11; 19.375 5 8 -3 ];

for IsDiagDom( A );

if isdom == 1

disp (['Matrix A is diagonally-dominant']);

elseif A = A(randperm(size(A, 1)), :); % Randomly swaps rows

return

end

end

end

Thank you a lot !

Sriram Tadavarty
on 20 Mar 2020

HI Eligijus,

The way the for loop is used here caused the issue. Update the second part of code as below and it works:

function [ A ] = DiagDom

A = [ 4 -28 -7 1; 4 -1 10 -1; -4 0 -3 11; 19.375 5 8 -3 ];

while(1) % Perform infinite loop, till you find the diagonally dominant matrix

if IsDiagDom (A) % If this is diagonally dominant, disp and break the loop

disp (['Matrix A is diagonally-dominant']);

break;

else

A = A(randperm(size(A, 1)), :); % Randomly swaps rows

end

end

end

Hope this helps.

Regards,

Sriram

John D'Errico
on 20 Mar 2020

Edited: John D'Errico
on 20 Mar 2020

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?

Row = ones(1,10);

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)

% takes a square matrix A and permutes the rows if possible so that A is diagonally dominant

[n,m] = size(A);

if n~= m

error('A is not square')

end

% test to see if a valid permutation exists

[maxrow,maxind] = max(abs(A),[],2);

if all(maxrow > (sum(abs(A),2) - maxrow)) && isequal(sort(maxind),(1:numel(maxind))')

% success is both possible and easy to achieve

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

Raghad
on 30 Apr 2020 at 6:36

Hello John.

Thank you for your solution it was very helpful.

I wanted to ask if it is possible to change the solution to accept matrices with a diagonally dominant condition like this:

"Diagonally dominant: The coefficient on the diagonal must be at least equal to the sum of the other coefficients in that row and at least one row with a diagonal coefficient greater than the sum of the other coefficients in that row."

For example if A = [0 1 1; 2 7 2; 4 1 1], I want to rearrange the matrix to be A = [4 1 1;2 7 2; 0 1 1]

I tried to change the code but I did find the solution yet.

Thank You.

Sign in to comment.

Anita Mundra
on 23 Apr 2020

hell Eligijus Rupsys

i am also looking for such loop code, but unable to trace out.

did you get solution for your problem.

as the code taht is mentioned is not running.

it is giving an error

"Error in DiagDom (line 5)

if IsDiagDom (A) % If this is diagonally dominant, disp and break the loop"

if you can please share the code with me.

my email id is: anitamundra26@gmail.com

Sign in to comment.

Sign in to answer this question.

Opportunities for recent engineering grads.

Apply Today
## 1 Comment

## Direct link to this comment

https://se.mathworks.com/matlabcentral/answers/511902-making-a-matrix-strictly-diagonally-dominant#comment_812692

⋮## Direct link to this comment

https://se.mathworks.com/matlabcentral/answers/511902-making-a-matrix-strictly-diagonally-dominant#comment_812692

Sign in to comment.