# Bounds on number of "non-metric" entries in matrices

MathOverflow Asked on January 1, 2022

Question:
what upper bounds are known on the number of non-metric entries of finite dimensional square matrices $$boldsymbol{A}inmathbb{R}^{ntimes n}$$ with strictly positive off-diagonal elements $$a_{ij}$$?

In this context $$a_{ij}$$ is defined to metric iff $$quad a_{ij}leqq a_{ik}+a_{kj},forall knotinlbrace i, jrbracequad$$ and non-metric otherwise.

I had posted the problem because I couldn't see how to solve it for some time but for some strange reason I found a simple answer not long after I put it on MO, so it is rather to be seen as a comment:

The basic idea for constructing an extremal example is to take a densest triangle-free graph and set its edgeweights to $$1$$ and augment it to a complete graph by adding edges of weight $$3$$.

Densest triangle-free graphs are $$K_{n,n}$$ with $$n^2$$ edges, implying that the number of non-metric edges that augment it to $$k_{2n}$$ is $$ncdot(2n-1)-n^2 = n^2-n$$ if the number of vertices is $$2n$$

Answered by Manfred Weis on January 1, 2022