MATLAB Answers

Saddle points of a 2D matrix

543 views (last 30 days)
Marco Nashaat
Marco Nashaat on 11 Feb 2020
Commented: Shaon Talukdar on 11 Oct 2020 at 1:08
the problem I'm working on is to find the saddle points of a matrix and now I'm trying this ...
  • nested loop to check every element
  • check if the element is the smallest in its column and the biggest in its row
  • if it is,print it into the matrix'indices'
  • if there was none,print empty matrix....and the code [row,col]=size(matrix); for I=1:row for j=1:col if matrix (I,j)==max(matrix, I)&&matrix (I,j)==min(matrix, j) indices=[i j;]: else indices=[ ] end end endsome help with the syntax please,thanks!!

  0 Comments

Sign in to comment.

Accepted Answer

Jon
Jon on 11 Feb 2020
Edited: Jon on 11 Feb 2020
Here is a simple approach. Note I define a saddle point as one that is either the largest in its column and smallest in its row or the smallest in its column and largest in its row. Maybe you only want to look for the second kind in which case you can modify the approach accordingly.
Also this code is quite inefficient. You could further optimize it by finding and saving the column maximums, column minimums, row maximums and row minimums before entering the loop.
You could also probably vectorize this further and not use a loop at all, but I think you wanted to see how the basic syntax would look.
% make a matrix to try algorithm on
% there are saddle points at 2,2 and 4,4
A = [10 12 7 3 12;
3 10 6 2 8;
12 24 17 6 10;
15 21 10 8 12;
1 18 22 4 15];
disp A
% get dimensions of the matrix
[numRows,numCols] = size(A);
% preallocate array to hold indices for saddle points, there can be at most two
indices = zeros(2,2);
% loop through rows and columns of matrix
numSaddle = 0; % counter
for iRow = 1:numRows
for jCol = 1:numCols
% check if it is the biggest element in its row and smallest
% element in its column
brsc = A(iRow,jCol) == max(A(iRow,:)) && A(iRow,jCol) == min(A(:,jCol));
% check if is the smallest element in its row and biggest
% element in its column
srbc = A(iRow,jCol) == min(A(iRow,:)) && A(iRow,jCol)== max(A(:,jCol));
if brsc || srbc
numSaddle = numSaddle + 1;
indices(numSaddle,:) = [iRow,jCol];
end
end
end
% delete off the unused entries in the indices array
indices = indices(1:numSaddle,:);
% display the result
disp(indices)
% display saddle points
for k = 1:numSaddle
disp(A(indices(k,1),indices(k,2)))
end

  5 Comments

Show 2 older comments
Marco Nashaat
Marco Nashaat on 11 Feb 2020
Thanks a lot It works perfectly
Rishi Diwan
Rishi Diwan on 23 May 2020
function indices=saddle(M)
indices=[]; c=1;
[row,col]=size(M);
for I=1:row
for j=1:col
if M(I,j)== max(M(I,1:col)) && M(I,j)==min(M(1:row,j))
indices(c,1)=I;
indices(c,2)=j;
c=c+1;
end
end
end
Shaon Talukdar
Shaon Talukdar on 11 Oct 2020 at 1:08
Great!!! It Worked.

Sign in to comment.

More Answers (6)

Sahil
Sahil on 4 Apr 2020
function indices = saddle(M)
saddle_m = zeros(size(M));
row_maxima = max(M, [], 2);
col_minima = min(M, [], 1);
indices = [];
for i = 1:size(M, 1)
for j = 1:size(M, 2)
if M(i, j) == row_maxima(i) && M(i, j) == col_minima(j)
saddle_m(i, j) = 1;
indices = [i, j; indices];
end
end
end
end

  1 Comment

Nihal Dwivedi
Nihal Dwivedi on 16 Jun 2020
thanks this worked perfectly

Sign in to comment.


fred  ssemwogerere
fred ssemwogerere on 11 Feb 2020
Hello, i think something like this should do nicely:
% To check which element is the smallest in its column, and biggest in its row, for a given matrix say,
% "b", you can first pre-allocate a matrix of zeros where the valid saddle points will be input.
indices=zeros(size(b)); % pre-alocating "indices" based on size of assumed matrix "b"
% Next determine the minimum values of each column of the matrix, "b"
b_colmin=min(b);
% Determine the maximum values for each row of "b" by first taking the transpose of "b"
b_rowmax=max(b');
% Check for membership of "b_colmin" in "b_rowmax"."lm" is a vector of lowest indices in "b_rowmax" for each value of "b_colmin" in "b_rowmax"
[~,lm]=ismember(b_colmin,b_rowmax);
% find the column indices of non-zero indices ("nzCol") in "lm", and the corresponding vector on non-zero values ("nzVec"). The vector "nzVec" in actual sense will be a vector of row indices for the saddle points.
[~,nzCol,nzVec]=find(lm);
% Input saddle points into marix "indices" based on indices
indices(nzVec,nzCol)=b(nzVec,nzCol);

  2 Comments

Marco Nashaat
Marco Nashaat on 11 Feb 2020
Thanks but I guess there might be a bug....when asking for membership let's say the maximum value of a row was actually equal to minimum of Irrelative column then "indices" will return the index of a wrong element!! correct me if I was wrong,thanks
fred  ssemwogerere
fred ssemwogerere on 11 Feb 2020
"indices" returns the values that are maximum in a row, but minimum in their column, at their indexed positions in an assumed matrix "b". However, if the aim is to only get the indices of the saddle points, then all you need will be: "nzVec" and "nzCol". You can write this into an array as [nzVec,nzCol].

Sign in to comment.


darova
darova on 11 Feb 2020
One way to use surfnorm
clc,clear
% generate some data
[X,Y] = meshgrid( linspace(-1,1,20) );
Z = X.^2-Y.^2;
[nx,ny,nz] = surfnorm(X,Y,Z); % normal vectors
[az,el,rho] = cart2sph(nx,ny,nz); % find azimuth and elevation
[~,ix] = max(el(:)); % find maximum elevation
mesh(X,Y,Z)
hold on
scatter3(X(ix),Y(ix),Z(ix),50,'r','filled') % saddle point
quiver3(X,Y,Z,nx,ny,nz,'b') % show normal vectors
hold off
axis equal

  0 Comments

Sign in to comment.


Ajijul Mridol
Ajijul Mridol on 27 Jun 2020
Edited: Ajijul Mridol on 27 Jun 2020
function indices=saddle(M)
[row,col]=size(M);
k=1;
for i=1:row
for j=1:col
%check if it is the biggest element in row and smallest in that column
if (M(i,j)==max(M(i,:)) | M(i,j)==M(i,:)) & (M(i,j)==min(M(:,j)) | M(i,j)==M(:,j))
indices(k,1)=i;
indices(k,2)=j;
k=k+1;
end
end
end
if k==1
indices=[]; %return an empty matrix if there is not saddle point
return
end
end

  0 Comments

Sign in to comment.


Sharnam Singhwal
Sharnam Singhwal on 27 Aug 2020
function indices=saddle(M)
[row,col]=size(M);
count=0;
indices=[];
for i= 1:row
for j= 1:col
if M(i,j)==max(M(i,:)) && M(i,j)==min(M(:,j))
indices=[indices;i j];
end
end
end
end

  0 Comments

Sign in to comment.


shubham nayak
shubham nayak on 3 Sep 2020
function indices=saddle(z)
[a,b]=size(z);c=1;
indices=[];
for i = 1:a
for j = 1:b
maxrow(i,j)=max(z(i,1:b));
if(maxrow(i,j)<=min(z(1:a,j)))
indices(c,1)=i;
indices(c,2)=j;
c=c+1;
end
end
end
end

  0 Comments

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!