How to sort rows of a 2D array, such that all elements along a diagonal are non-zero?

Thank you for looking at my question.

The problem: I have a square matrix containing random 0s and 1s, and I need to swap the rows around, so that all elements along one of the diagonals are 1s. (every row and column contains at least one 1, to make sure this is possible)

Is there any function that will be able to do this automatically or can you suggest how to go about doing it with code...?

[Image Analyst]

What if it can't be done, like you have a 4 by 4 matrix of all 0's (it could happen randomly!)? By the way, this kind of quirky operation sounds like a homework problem. Is it? Or do you have a real world "use case" for it? If it's homework, assign a tag of homework.

[Jan]

@Image Analyst: The problem is feasible due to the statement, that every row and column contains a 1.

@Maria: How large is the matrix? For 5x5 matrices a brute force approach is the fastest when you consider the time for programming in the total time to solve the problem. When you are talking of 1e5 x 1e5 matrices, another solution will be better.

[dpb]

First thought (unimplemented) --

Find rows that fail, determine distance from diagonal to a '1' for the row and circshift same that number of times--oh, that has problem of screwing up a previously ok row in blind app.

But, just ensuring there's at least a '1' on each row and at least every column has a '1' also doesn't mean it's solvable--that requires a corollary condition of there being at least one row w/ a one in each column for to match with a row. The "at least one" only applied globally doesn't ensure they're necessarily distributed as needed.

That observation leads to another solution--find the row w/ the one in each column then move them where they needs must be if they're not ok already.

ADDENDUM:

Actually, if the "every row/column contains at least one one" makes it solvable, then just circshift the row(s) w/o a one on the diagonal left/right until that one is...as noted above, that condition alone isn't sufficient w/o being allowed to reorder, so if can to make it solvable then just do so.

[Maria]

Thank you everyone for your help.

@ Image Analyst - my script already has an if statement for the case that all elements are 1s. This is the best case scenario really, because I'm guaranteed a non-zero diagonal. The real world use for it is solving linear systems using an iterative method, which requires the diagonals to be non-zero.

@ Jan Simon - The code should ideally work for matrices of dimensions of the order of 10s or 100s at the most. Time is not an issue. Can you suggest how to implement a brute force approach?

@ dpb - I see what you mean about the equation being solvable. Thanks. However, by nature of the problem, the matrix in question is not likely to have many 0s, so we can assume it is solvable.

After all of your suggestions my plan now is to try to just circshift rows, until all elements along the diagonal are 1s...and break after a certain amount of iterations and display an error message in that case.

Could anyone suggest how to write this code?

[Image Analyst]

But if you do circshift, you're not using your original row vectors anymore. If you shift it, it's a different pattern. Do you care about that? Also, there may be multiple solutions, such as the case where the vast majority of the array is 1's. Is any solution okay, such as the first one you find?

[dpb]

'Pends on which way the circshift is done... :)

My first thought was rows; it was only if the condition for "solvable" is as given the second case where the 1 and 1 is sufficient that it would imply shifting within a row is allowable to be solvable in general. That was a query/observation that OP has to answer along with yours for enough info to write a unique solution.

[Maria]

The condition is that the rows should be left intact (shifting within rows is not allowed) - so whole rows should be swapped with each other, columns cannot be swapped as this would change the order of the elements in the rows.

I am looking for any solution where the diagonals are non-zero - so the first will do. I just need those elements along the diagonal to be non-zero so I can proceed with the rest of the code.

I have come to the conclusion that circshift will not work because it doesn't do random swaps, but only collectively moves all rows up or down, which won't work in all cases.

[Image Analyst]

Now you tell me. Well I guess my answer was a big waste of time. By the way, is this homework? If so, tag it as homework.

[Maria]

I'm sorry, I thought the way I posed the question was clear enough :( This is a part of my university assignment that I'm stuck on.

[Image Analyst]

I think this might be one of those problems that looks deceptively easy at first but once you get into it, it is revealed to be a lot harder, kind of like the knapsack problem or the traveling salesman problem.

[Alberto]

I will comment my answer (somebody has to).

You can prove by induction that the property of 'having a 1 in each row and each column' can be transformed in the desired way (really easy prof, i promise).

So you have to cross the matrix, looking in every step k a row :

1) with an element 1 in the k-th and

2) the remaining matrix has the same property I talked before.

It will return how the matrix's rows has to be reordered.

Answer 1

[lvn]

For reference, here is a solution using the backtracking. The main algorithm part is around 20 lines.

This is the initial solution
xoriginal =
     1     1     0     0     1
     1     1     0     0     1
     0     0     1     0     0
     0     1     1     1     0
     0     1     0     0     1
Shuffled version
x =
     0     0     1     0     0
     0     1     0     0     1
     1     1     0     0     1
     1     1     0     0     1
     0     1     1     1     0
This is the solution found
xsol =
     1     1     0     0     1
     0     1     0     0     1
     0     0     1     0     0
     0     1     1     1     0
     1     1     0     0     1
Order of the rows: 
per =
     3     2     1     5     4

Code:

function answw2
    n=5 ; %Generate a matrix that fulfills the requirements
    xoriginal=diag(ones(n,1));
    y=rand(n,n);
    xoriginal(y<(n/2-1)/(n-1))=1; %so that on average as much 0's as 1's (so sum(x(:))/n^2 = 0.5 on average)
    x=xoriginal(randperm(n),:); %And permute it so that we have a challenge

      %Alternatively use x=round(rand(n,n)) for a random 1/0 matrix with no guaranteed solution

      %Now put the rows with fewest 1's on top, as it is best to start with these
      [~,isorted]=sort(sum(x,2));
      x=x(isorted,:);

      %And now find the solution
      per=first(x,0,1:n);

      %Output the solution
      disp('This is the initial solution'); xoriginal
      disp('Shuffled version'); x

      if ~isnan(per)
          disp('This is the solution found'); xsol(per,:)=x
          disp('Order of the rows: '); per
          assert(all(diag(xsol)==1)) %Sanity test
      else
          disp('No solution found !');
          return
      end;
  end

function solution=first(X, row, whichrowstoplace) %For a single root, loop over all leaves
solution=[];
for nr=1:length(X)-row %Try all possibilities to place the row + 1 in the correct position
    solution=next(X, row+1, nr, whichrowstoplace);
    if ~isnan(solution) %We got ourselves a solution, we can go back up a level
        return
    end
end
end

function solution=next(X, row, nr, whichrowstoplace)
firstrow=X(row,:);           %Take the row
onelocation=find(firstrow);  %And find the location of the ones
leaves=onelocation(ismember(onelocation,whichrowstoplace));  %We are only interested in the ones that we still need
if nr>length(leaves)         %You exhausted all possible tests, the row cannot be placed and therefore root must be bad
    solution=NaN;
else                         %Otherwise leaves(nr) is the next (candidate) solution
    solution=[leaves(nr) first(X, row, whichrowstoplace(whichrowstoplace~=leaves(nr)))];
end;
end

Answer 2

[Alberto]

I created the function check(A), so i can check if the property 'every row and column are not all zeros'. Its useful later:

function condition=check(A)

cf=zeros(1,length(A));

for k=1:length(A) if sum(find(A(k,:)))==0 sum(find(A(:,k)))==0 cf(k)=0;

    else
        cf(k)=1;
    end

end

if sum(cf)==length(A) condition=1;

else condition=0; end

end

Now you have a matrix A, use this script:

rowspermute=zeros(1,length(A));

 B=A

 mirango=1:length(A)

    for k=1:length(A) % kth column

        for j=mirango

            miraux=mirango;

            miraux(find(mirango==j))=[];

           if A(j,k)==1 &&  check( A(miraux   ,  k+1:end)    )

               rowspermute(k)=j;

               mirango=miraux;

               break

           end

        end

        if rowspermute(k)

        A(rowspermute(k), :)=zeros(1,length(A));

        end   
    end

rowspermute % has the rows to reorder

[dpb]

Your check function boils down to

function condition=check(A)
  condition=all(any(A) & any(A,2).');

I've not read rowspermute carefully... And, I assertion re: solvability is ok as stated by OP.

[Alberto]

The idea is implemented, but of course can be coded better.

OP?

[Maria]

Could you please explain what these lines of code mean?

if rowspermute(k)

        A(rowspermute(k), :)=zeros(1,length(A));
        end

Sorry for late comment.

[Alberto]

The idea behind the code is selecting a row with 1 in the desired position, and that can be eliminated in the matrix without loosing the property (ones in every row and column).

At first i tried to erase the row in the matrix so the same row couldn't be chosen twice, but it was tricky to track which number of the original rows in matrix A.

I thought putting zeroes in that row was an elegant solution to prevent that row to be chosen again.

The if block has the porpose to be sure a row was selected before.

Answer 3

[Image Analyst]

If you're willing to use circshift, then try this:

clc;
rows = 20;
columns = 20;
m = randi(2, [rows, columns])-1
output = zeros(size(m));
for row = 1 : rows
  % Get this row.
  thisRow = m(row, :);
  % Shift it until we get a 1 in column "row".
  for colShift = 0 : columns - 1
    % Shift this row by some amount.
    shiftedRow = circshift(thisRow, colShift, 2)
    % See if we shiftwed a 1 into the diagonal element at column "row"
    if shiftedRow(row) == 1
      % It's a 1, so we're done.
      output(row, :) = shiftedRow;
      % Quit shifting this row.
      break;
    end
  end
end
output % Display in command window.

[dpb]

Thinking about this a little more...

First, the test for complete is

all(diag(x)) | all(diag(fliplr(x)))

Solvability is as given above.

For a given array, there's one other condition that can be eliminated/solved for to minimize the remainder and that is any row containing only one nonzero element must be placed on the row in which column that element exists and can't be moved again.

After that, you've got N choices of the remaining rows with N locations that will satisfy the condition. Unless the sparsity is quite low, I'd think if your solution doesn't account for the minimal cases first you'd likely end up with a "first-come, first served" solution running out of options before getting done.

[Image Analyst]

Not sure if this is related to my answer. She now says that every row is guaranteed to contain at least one 1, and she changed her mind and said not to use circshift, so my answer is not applicable anymore.

[dpb]

No, it wasn't/isn't related to yours and I'd realized my leading down the rabbit hole of circshift was a trip into Alice-land.

It just came to me what is related to my initial thought on solvability is that there are only N permutations of the rows w/ N ones as to where they can go with the limiting case of, of course, there being only the single nonzero value in a row in which case it has only one place it can go. That seemed to me likely to be a cleaner way to attack it by taking care of the minimally populated rows first where the limitations are the most restrictive while still have flexibility with the more densely populated. If one were, otoh, to simply work thru from the top down placing one with a value where it needed to be w/o paying attention to the global population, it would seem likely would get to a point had used up everybody with a one where needed it and so would have to retrace steps. At least doing the minimum ones first avoids that.

[lvn]

The general backtracking https://en.wikipedia.org/wiki/Backtracking algorithm seems most suitable for this. As mentioned before, start with the rows which can only be placed in one position, than with those in two positions (try one, and backtrack as needed), etc..

[Image Analyst]

Good information. I think you're right. Nice to know there's an organized way for solving it. Seems a bit tough for a homework problem though - glad I don't have that teacher. I started thinking about graph solving algorithms and thought it had to be like one of them. Personally I only know about Djikstra and A* though there are lots of similar kinds of graph search algorithms. (Funny, after I had independently "discovered" A* as part of my Ph.D. research, I found out that it had already been invented. Bummer. Lost out on that glory.)

[Maria]

Thank you everyone. I think the question is solved now with the help of my little brother, who figured out a way to get past the circshift problem. I have not finished coding it but will post on here when I'm finished for anyone who's still interested.

The code works by going over each row's diagonal A(i,i) and if theres a 0 in that row's diagonal it proceeds to check whether the elements below that row in the corresponding column (A(i+1:end,i) contain any 1s or if its all 0s. Then for each case there is a different shifting pattern, which ensures that all rows are used and no rows become 'stuck' at the top.

It works on paper with a particularly nasty matrix that my previous code could't rearrange, but it is expected to have 10+ loops....

My original idea was something along the lines of that backtracking algorithm but I had trouble writing the code. As you may have guessed, I only started using Matlab recently and have no previous coding experience.