Pair a row index with a column index

Here is my problem:

I created a matrix that has N number of rows and M columns. No I want to match the n-th row with the m-th coumn but each row_index can have only one coumn_index as a match. Here is how the matrix looks like:

     |  1     2       3       4       5       6       7       8       9       10
-----|-----------------------------------------------------------------------------
1    |  8	9	1	6	4	19	12	9	3	1    
2    |  20	21	11	18	16	31	NaN	21	15	NaN
3    |  NaN	NaN	NaN	NaN	NaN	NaN	NaN	NaN	14	NaN
4    |  11	12	2	9	7	22	NaN	12	6	NaN
5    |  11	12	2	9	7	22	9	12	6	4
6    |  8	9	1	6	4	19	12	9	3	1
7    |  8	9	1	6	4	19	12	9	3	1
8    |  14	15	5	12	10	25	6	15	9	7
9    |  4	5	5	2	0	15	16	5	1	3
10   |  4	5	5	2	0	15	16	5	1	3

For instance row index 3 has only one match with column index 9, but row 1 can be match with all coumns. I want to do this matching with the following rule:

• Each column can have only one row match

The final result should be something like this :

Row_Index    Column_Index
1                7      
2                8
3                9
4                6
5                5
6                4
7                2
8                1
9                3
10               10

I have no idea where to start.

Thank you for your help!

[Guillaume]

By table, I assume you mean a matrix and not an actual matlab table.

What does matching a row with a column mean?

Why has row 3 got only one match with row 9?

What do the number mean in your matrix?

Please use valid matlab syntax in your examples rather than inventing your own ambiguous notation. And show us the desired result.

[Georgios Pyrgiotakis]

You are very correct! It is a matrix. My matching I mean the index. so Row 3 - Column 9

The number is a scorring (which I think is irrelevant to the question I am asking). Numbers over a certain number were cut off (that's why there is NaN in the matrix). I will also revise the question above.

Thanks for the input!

[Guillaume]

That's better but I still have no idea what you mean by matching. Why did you match row 1 with column 7 in your example?

[Georgios Pyrgiotakis]

There can be many solutions to this, I only want one. In this example as you correctly pointed out row 1 can be matched with all columns but I picked 7 randomly. Now 7 cannot be used for any other row. If I had picked 9 that means that row three will have no match so that was not a valid choice.

Is this more clear? I don't really know how to describe the problem mathematically.

[Joel Handy]

So doesnt every row match with every column unless it has a NaN?

[Georgios Pyrgiotakis]

Yes. Exactly. But it once a row-colum pair is made you can't reuse any of the two.

Answer 1

[Jon]

This can be categorized as a Matching problem. In particular it can be mapped to a Matching problem on a Bipartite Graph. Let's call your matrix A. Then we consider a graph where one set of nodes are the row numbers and the other set of nodes are the column numbers in A. An edge in this graph connects the node for the ith row with the node for the jth column if there is a column element in the ith row and jth column of your matrix. We are interested in finding a largest cardinality matching (most matching edges) between the row and the columns.

There is a MATLAB File Exchange submission https://www.mathworks.com/matlabcentral/fileexchange/23159-maximum-cardinality-matching that claims to solve exactly this problem (actually it solves a more general problem and is not limited to Bipartite Graphs, but it will work for them as a specicial case, could be other programs out there that would be more efficient for just solving Bipartite Matching problems, but this one will work). Here is some code that shows how you could map your original problem into a matching problem on a Bipartite graph, and then applies the FEX submission to solve the problem. Most thanks go to the authors of the FEX submission where the hard work is done. This is the only experience I have using this FEX submission, as usual you would have to verify that it works properly to solve your problem, but it seemed to work OK for this one example, so that's encouraging.

A = [...
8	9	1	6	4	19	12	9	3	1
20	21	11	18	16	31	NaN	21	15	NaN
NaN	NaN	NaN	NaN	NaN	NaN	NaN	NaN	14	NaN
11	12	2	9	7	22	NaN	12	6	NaN
11	12	2	9	7	22	9	12	6	4
8	9	1	6	4	19	12	9	3	1
8	9	1	6	4	19	12	9	3	1
14	15	5	12	10	25	6	15	9	7
4	5	5	2	0	15	16	5	1	3
4	5	5	2	0	15	16	5	1	3];

% determine dimensions of matrix
[numRows,numCols] = size(A); 
assert(numRows == numCols,'matrix must be square'); % make sure matrix is square
N = numRows; %number of rows and columns



% loop through rows determining if they have any common elements (ignoring
% NaN)with each column, record results in matrix whose i,j element is 1 if
% row i has any elements in common with row j, and otherwise is zero
adj = zeros(N);

for iRow = 1:N
    for jCol = 1:N
        % use set intersection to determine if they have any elements in
        % column, if they do intersection is nonempty
        adj(iRow,jCol) = ~isempty(intersect(A(iRow,:),A(:,jCol)));
    end
end

% consider as Bipartite Graph Matching Problem
% define graph with 2*N nodes, nodes 1 to N represent the rows
% nodes N+1 to 2*N represent the columns
% there is an edge in the graph from node i to node j if row i and column j
% have elements in column.

% define symmetric adjaceny matrix (edges are not directed)
Adj = [zeros(N) adj;adj' zeros(N)]

% use MATLAB fex (File Exchange) submission https://www.mathworks.com/matlabcentral/fileexchange/23159-maximum-cardinality-matching
% to solve
[match] = card_match(Adj);

% we are only interested in the first N elements of match, these tell us
% connections from rows to columns
match = match(1:N);

% since in the graph the node numbers for the columns go from N+1 to 2N we
% subtract of N to get back the associated column numbers
match = match - N;

% display the result
% the match(i) = j means that row i can be matched with column j
disp(match)

[Georgios Pyrgiotakis]

Sorry for the late response! I could not have my work computer during weekends! I will try your solution! Thank you so much.

[Georgios Pyrgiotakis]

Works like a charm! Thank you so much!

[Jon]

Glad to hear. I learned something about graph representations of "matching problems" too. Turns out lots of practical problems can be framed as matching problems. Very interesting topic.

[Georgios Pyrgiotakis]

Hi Jon,

I am looking in more detail in this and it is at teh right track, bust still there are some small issues. In the above example I get a result that is:

6     5    10     3     9     7     4     1     2     8

But if you look closely Row 3 cannot be matched with Column 10 since it is an NaN;

Am I missing something? I tried to troubleshoot the code, but after 2 days I can figure it out. Why is that happening?

Thank you so much for your support!

[Georgios Pyrgiotakis]

I figured a solution. It has to do with the way the adj table is calculated. I changed it in a less elegant way (changed the name to adj1):

adj1 = zeros(N);
for iRow = 1:N
    for jCol = 1:N
        if isnan(A(iRow,jCol))
            adj1(iRow,jCol)=0;
        else
            adj1(iRow,jCol)=1;
        end
    end
end

This worked repeatidly!

[Jon]

As you noted the solutions aren't uniqe. Apparently there is some randomness in how the fex solver works because I get different answers (from among the many possible solutions) each time I run. I made a loop to evaluate the match vector 100000 times and never found a solution where match(3)==10.

In fact in every case match(3) had a value of either 1 or 9 which makes sense since row 3 only has one value that is numerical, and this value is 14. Only columns 1 and 9 have a 14

Can you please attach a copy of the exact program you used to generate the above solution with match(3) ==10?, can you reproduce the problem?

[Georgios Pyrgiotakis]

Everytime I run it it a different answer as you said. But with the previous code I could get repeatidly at least one mistake. The new code seems to be working for all cases. I still try to find the reason for the difference.

[Jon]

The approach I used to generate the adjacency matrix was a little more general, so depending on your situation it might be applied more broadly, but for your special situation I agree the ith row will match the jth column unless the i,j element is NaN. So you could generate the adjacency matrix with your alternative formulation.

I'm still puzzled however how you ever got that example where the third row matched to column 10.

I have attached my test code. Note it executes 100,000 times. So far I haven't seen a single case where we don't match row 3 either to column 9 or column1.

Maybe you can compare my code to yours to see if you see any differences.

[Jon]

Actually, depending upon how you define a valid matching, your method for generating the adjacency matrix may not be correct.

I assumed by a valid match you meant that the ith row and jth column were a valid match if they had any elements in common. So with this definition row 3 is a valid match with column 1 as they have 14 as a common element.

If this is also your definition, then your approach for generating the adjaceny matrix is not correct. It will find that row 3 column 1 of A is NaN and set the adjacency matrix element to zero.