Find saddle points in Matlab

Question

I have to write a function called saddle that finds saddle points in the input matrix M. For this problem, a saddle point is defined as an element whose value is greater than or equal to every element in its row, and less than or equal to every element in its column. The function should return a matrix called indices that has exactly two columns. Each row of indices corresponds to one saddle point with the first element of the row containing the row index of the saddle point and the second column containing the column index. The saddle points are provided in indices in the same order they are located in M according to column-major ordering. If there is no saddle point in M, then indices is the empty array. Here's what I have up until now:

% function indices = saddle(M)
% Definition of a test matrix M:
M = [0.8147  0.1270  0.6324  0.2785; ...
     0.9058  0.9134  0.0975  0.5469];

[ rows,cols ] = size(M);

[valR,posR] = max(M,[],2);
[valC,posC] = min(M,[],1);
indices= [];

for i = 1:length(posR)
    for j = 1:length(posC)
        if posR(i) == posC(posR(i))
            indices= [indices; posR(i),posC(i)];
        end
    end
end

As I commented on the code, I have defined a test matrix that has a saddle point on position (1,1), but the code is not working properly because it returns

What am I doing wrong?

A couple of hints: 1) You aren't using the variable 'j'. Maybe you don't need that loop. 2) You are comparing posR(i) to posC(posR(i)) with an if statement. The maximum value of posR (for your M matrix) is 4, but the maximum value for posC is 2. So if your row maximum happens to be at index 4 there is no way for that comparison to be true. That indicates that your if statement is probably not comparing what you want it to. — ioums

Unknown Unknown · Accepted Answer · 2015-06-10T23:23:05

You only need one loop, not a double loop. All candidates for saddle point are entries with indices (i, posR(i)). Such an entry is a saddle if it's also smallest in its column, which means i == posC(posR(i)).

You also output incorrect numbers: should be (i, posR(i)).

for i = 1:length(posR)
    if i == posC(posR(i))
        indices= [indices; i, posR(i)];
    end
end

Note that your algorithm ignores the fact that some entries could be equal: the functions max and min only give you the first maximal or minimal entry. For floating point numbers this may be okay to ignore, but for integers this could be pretty important.

Here is an approach that has no for loop and accounts for possible equality:

saddles = (kron(valR,ones(1,cols))==M).*(kron(ones(rows,1),valC)==M);
[I, J] = find(saddles);

Each of two factors on the right is a 0-1 matrix with 1s marking the candidates for a saddle. The entrywise product results in a 0-1 matrix where 1s mark the saddle points. Then the find command returns the indices of the saddles.

E.g., with the test example M = [1 2 1 2 ; 5 3 4 3]

saddles =

     0     1     0     1
     0     0     0     0

I =

     1
     1


J =

     2
     4

Find saddle points in Matlab

1 Answers