# Is there a way to normalize a similarity matrix by row and column in a way such that only one entry per row or column is approximately 1

I am computing similarities between 2 vectors. My goal is to have approximately 1 matching sample with similarity ~1, for each sample, without having any samples that are similar to many other samples.

I've tried a greedy, binary approach (akin to finding the nearest neighbor), where you take the most similar pair (x, y), set S(i==x, j==y)=1, set all others in that specific row and column to 0, (ie S(i==x,j!=y)=0 and S(i!=x,j==y)=0), and move on to the next highest pair.

However, I'd like a technique though that performs this in a smoother and more "mathematically rigorous" way.

As an example, take these 5 vectors,

[1,1,0], [1,1,5], [3,3,6], [1,1,-5], [3,3,-6]

I'd want [1,1,5] and [2,2,6] to be similar to each other and likewise with [1,1,-5] and [2,2,-6], but with [1,1,0] not very similar at all. However, as an example, using a normalized euclidean distance gives a similarity matrix where the [1,1,0] in the middle ends up being kind of similar to everything.

[[1.0, 0.6, 0.4, 0.6, 0.4],
[0.6, 1.0, 0.8, 0.2, 0.1],
[0.4, 0.8, 1.0, 0.1, 0.0],
[0.6, 0.2, 0.1, 1.0, 0.8],
[0.4, 0.1, 0.0, 0.8, 1.0]]


(Other distance metrics end up giving kind of the same thing in different situations.) What I'm looking for is a general way to reweight that matrix to look something more like

[[X.X, 0.3, 0.3, 0.1, 0.1],
[0.3, X.X, 0.9, 0.0, 0.0],
[0.3, 0.9, X.X, 0.0, 0.0],
[0.1, 0.0, 0.0, X.X, 0.9],
[0.1, 0.0, 0.0, 0.9, X.X]]


Is there a standard technique to perform this normalization?