Is there a name for this family of matrices?

Question

Let $0<a_1<a_2<\cdots<a_n$ and let $A$ be the symmetric $n\times n$ matrix with ${ij}^\text{th}$ entry $A_{ij}=\min\{a_i,a_j\}$. For example, if $a_i=i$ for each $i\le n=5$ then $$A=\begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 & 3 \\ 1 & 2 & 3 & 4 & 4 \\ 1 & 2 & 3 & 4 & 5 \\ \end{bmatrix}.$$ Is there a name for the family of matrices with this structure?

Answer 1

I don't know a particular name for these matrices but they are special cases of matrices which have been considered in lattice theory. More precisely, let $(L,\wedge)$ be a finite semilattice and $\phi:L\to \mathbb R$ any function (one can replace $\mathbb R$ by any commutative ring). Now consider the matrix $$A:=(\phi(x\wedge y))_{x,y\in L}.$$ Your matrices are obtained by choosing for $L=\{1,\ldots,n\}$ with its natural order and $f(i)=a_i$ because then $f(i\wedge j)=a_{\min(i,j)}=\min(a_i,a_j)$.

Lindström (Determinants on semilattices. Proc. Amer Math. Soc. 20 (1969), 207–208) and, independently Wilf (Hadamard determinants, Möbius functions, and the chromatic number of a graph. Bull. Amer. Math. Soc. 74 (1968), 960–964) computed the determinant as $$\det A =\prod_{x\in L}\left(\sum_{y\in L}\mu(y,x)\phi(y)\right)$$ where $\mu$ is the Möbius function on $L$. In your case this means $$ \det A=a_1(a_2-a_1)\ldots(a_n-a_{n-1}). $$

Answer 2

These are also a special case of matrices that are considered in phylogenetics, and in potential theory on graphs.

---

In phylogenetics, one studies rooted trees which are meant to represent the evolutionary history of a collection of organisms. Usually the leaf vertices represent modern-day organisms, while internal vertices represent ancestral organisms. The cophenetic similarity of two organisms $x$ and $y$ is the distance from the root to their most recent common ancestor, which we could denote as $x \wedge y$. The matrix $A$ in your question is the cophenetic similarity matrix for a tree consisting of a single path descending from the root, with edge lengths $a_1, \ldots, a_n$.

The cophenetic similarity matrix, indexed by all vertices of a rooted tree, is a special case of the meet matrix of a finite meet semilattice $L$ described in Friedrich Knop's answer, when $L$ is "tree shaped" (i.e., when $L$ does not have joins between any incomparable elements). However, an important caveat is that in phylogenetics one is often concerned with the cophenetic similarities between leaf vertices (i.e. modern-day organisms) only, which defines a submatrix of the meet matrix not covered by Lindström's theorem on the determinant of meet matrices.

In the phylogenetics literature, the cophenetic similiarity matrix has also been termed the ancestral matrix or the LCA matrix ("least common ancestor") of a rooted tree. In the following two papers, the former investigates results about eigenvalues of such matrices, and the latter gives an application to phylogenetic inference.

E. O. D. Andriantiana, K. Dadedzi, and S. Wagner, Ancestral matrix of a rooted tree, Linear Algebra Appl. 575 (2019) 35-65.

I. Gronau and S. Moran, Neighbor joining algorithms for inferring phylogenies via LCA distances, J. Computational Biology 14 (2007) 1-15.

---

In graph theory, there is a discrete Laplacian operator on any graph, which is analogous to the Laplacian operator on Euclidean space (or more generally on a Riemannian manifold). The Green's function on a manifold is the function that is essentially an "inverse" of the Laplacian operator. For a graph, the analogue of the Green's function is often referred to as the "potential kernel" or "potential function" or "$j$-function". For a reference, see:

R. de Jong and F. Shokrieh, Metric graphs, cross ratios, and Rayleigh's laws, Rocky Mountain J. Math. 52 (2022) 1403-1422.

The matrix $A$ in your question is a matrix of $j$-function values for a path graph. When the graph is a tree, the $j$-function values can be expressed in terms of shortest-path distance, while for a general graph, the $j$-function values are related to effective resistance in the sense of electrical networks.