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

Question:
what upper bounds are known on the number of non-metric entries of finite dimensional square matrices $$\boldsymbol{A}\in\mathbb{R}^{n\times 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 k\notin\lbrace i, j\rbrace\quad$$ and non-metric otherwise.

• In the other direction (i.e., forming a metric matrix), you may find doi.org/10.1137/060653391 interesting Commented Jun 23, 2020 at 21:20
• @SteveHuntsman's reference: Brickell, Dhillon, Sra, and Tropp - The metric nearness problem. Commented Jul 24, 2020 at 17:45
• I think the requirement $k\not\in\{i,j\}$ is slightly confusing: It competes with the quantifier $\forall$ in the attention of the reader. I think the question can be clarified by adding : "The requirements $k\not\in\{i,j\}$ is equivalent to the requirement that all diagonal entries are maximal (or something similar)". Commented Aug 19, 2021 at 15:51

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 $$\ n\cdot(2n-1)-n^2\ =\ n^2-n$$ if the number of vertices is $$2n$$
• If I understand your definition right, then the inequality $a_{ij}>a_{i1}+a_{1j}$ already makes $a_{ij}$ with $i,j>1$ non-metric, so in this case you can easily have only $2(n-1)$ metric elements in the whole $n\times n$ matrix: just those in the first row and the first column off the diagonal. However, judging from the discussion in this thread so far it looks like I misunderstand something, so, please, correct me if I'm wrong. Commented Aug 19, 2021 at 14:29
• It is almost settled. It is clear now that the minimal number of metric elements is $\ge n$ (every row/column contains at least one) and $\le 2(n-1)$ (my example), but there is still a 2-fold discrepancy between these bounds... Commented Aug 21, 2021 at 1:19