# Parsimony and the rank of a flattening matrix

Jandre Snyman  Department of Mathematics and Statistics, University of Otago,
Dunedin, New Zealand. Colin Fox  Department of Physics, University of Otago,
Dunedin, New Zealand.  David Bryant  Department of Mathematics and Statistics,
University of Otago, Dunedin, New Zealand. email<EMAIL_ADDRESS>phone: +64 34797889. (Corresponding author)

###### Abstract

The standard models of sequence evolution on a tree determine probabilities
for every character or site pattern. A flattening is an arrangement of these
probabilities into a matrix, with rows corresponding to all possible site
patterns for one set $A$ of taxa and columns corresponding to all site
patterns for another set $B$ of taxa. Flattenings have been used to prove
difficult results relating to phylogenetic invariants and consistency and also
form the basis of several methods of phylogenetic inference. We prove that the
rank of the flattening equals $r^{\ell_{T}(A|B)}$, when $T$ is binary, $r$ is
the number of states and $\ell_{T}(A|B)$ is the parsimony length of the binary
character separating $A$ and $B$. A similar formula holds for non-binary
trees. These results correct an earlier published formula.

Since completing this work, we have learnt that an equivalent result has been
proved much earlier by Casanellas and Fernández-Sánchez [11], using a
completely different proof strategy.

##  1 Introduction

Behind any statistical inference in phylogenetics is a model of describing the
evolution of the states (alleles/nucleotides/amino acids) observed at each
site in the alignment. Under the standard model, this evolution is determined
by three types of parameters: the phylogeny itself, the distribution of the
state at the root and the transition probabilities along each edge. Together
these generate the joint distribution for the state at each leaf, which in
turn corresponds to a column of the alignment (reviewed in [10, 15]).

Figure 1:  An example of patterns or sites on a four taxa tree. The 16
possible patterns are listed in the table on the right - any one of these
could be the pattern for a particular site.

An assignment of states to the taxa is often called a pattern. If there are
$r$ states (say $r=2$ for binary, $r=4$ for nucleotide, $r=20$ for amino
acids) and $n$ taxa then there are $r^{n}$ possible patterns. In the example
in Figure 1 we have $r=2$ and $n=4$, so $r^{n}=16$ possible pattern for the
joint distribution. Let $p_{i_{1}i_{2}i_{3}i_{4}}$ denote the joint
probability of pattern $i_{1}i_{2}i_{3}i_{4}$, that is the probability under
the model of observing state $i_{1}$ at leaf $1$, $i_{2}$ at leaf $2$ and so
on. We can think of these as elements of an $r^{n}$ dimensional vector

$\left[\begin{matrix}p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}\\\
p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}\\\
p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}\\\
\vdots\\\
p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\end{matrix}\right]$
(1)

or indeed as a $2\times 2\times 2\times 2$ multidimensional array or tensor.
Alternatively we can reshape the vector into a matrix, such as

$\left[\begin{matrix}p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\\\
p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\\\
p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\\\
p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\end{matrix}\right].$
(2)

In this matrix, the rows correspond to the $r^{2}$ possible ways of assigning
states to the first two taxa while the columns correspond to the $r^{2}$
possible ways of assigning states to the third and fourth taxa. A matrix of
this form is called a flattening. In tensor terminology, the flattening is an
example of an unfolding of the tensor of pattern probabilities. The idea was
introduced into phylogenetics by Pachter and Sturmfels [17] and developed
extensively by Allman and Rhodes to solve a wide range of mathematical
problems in phylogenetics [18, 1, 4, 3, 5, 6, 7, 8, 9].

We can construct a flattening for any partition $A|B$ of the set of taxa into
two non-empty parts. The rows of the flattening are indexed by all $r^{|A|}$
ways of assigning a state to the taxa in $A$ and the columns are indexed by
all $r^{|B|}$ ways of assigning a state to the taxa in $B$. Each entry equals
a term $p_{i_{1}i_{2}\cdots i_{n}}$ with each state $i_{k}$ determined by the
row if $k\in A$ and by the column if $k\in B$. We denote this matrix
$\mathrm{flat}_{A|B}$. The matrix in (2) is
$\mathrm{flat}_{\\{1,2\\}|\\{3,4\\}}$ and corresponds to the split
$\\{1,2\\}|\\{3,4\\}$. The flattening for split $\\{1,3\\}|\\{2,4\\}$ is

$\mathrm{flat}_{\\{1,3\\}|\\{2,4\\}}=\left[\begin{matrix}p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}\\\
p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\\\
p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}\\\
p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\end{matrix}\right]$

and the flattening for $\\{1\\}|\\{1,2,3\\}$ is

$\mathrm{flat}_{\\{1\\}|\\{2,3,4\\}}=\left[\begin{matrix}p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\\\
p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}\mbox{\tiny$\mathtt{Y}$}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}{\mbox{\tiny$\mathtt{R}$}}}&p_{\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}\mbox{\tiny$\mathtt{Y}$}}\end{matrix}\right].$

An important property of flattenings from phylogenies is their rank. Suppose
that $e$ is an edge in a phylogeny. Removing $e$ partitions the tree, and
hence the set of leaves, into two parts, inducing a partition $A|B$ of the set
of taxa. We say that $A|B$ is a split of the tree corresponding to edge $e$.
Allman and Rhodes [6] (Proposition 11) proved that, under minor assumptions,
if $A|B$ is a split in the tree then the rank of $\mathrm{flat}_{A|B}$ is at
most $r$, while if $A|B$ is not a split of the tree then the rank of
$\mathrm{flat}_{A|B}$ is at least $r^{2}$.

Because of this property, flattenings and their ranks have played a prominent
role in the mathematics of phylogenetics, particularly with respect to the
development and construction of phylogenetic invariants [7, 3, 17]. Roughly
speaking, a phylogenetic invariant for a tree is a function on vectors of
pattern probabilities such as (1) which is zero when the probability
distribution comes from that tree and non-zero otherwise.

Flattenings have also led to methods for inferring phylogenies directly. In an
original and influential chapter, Eriksson [14] outlines an efficient method
for inferring phylogenies with few assumptions about the evolutionary process.
The SVD quartets method [13] uses flattenings to infer trees for subsets of
four taxa, subsequently assembling these four-taxa trees into one for the
complete set of taxa. The method is statistically consistent even in the
presence of incomplete lineage sorting. Quartet-based approaches based on
flattening have also been developed by [16, 12]. Allman, Kubako and Rhodes
propose the ranks of flattenings as a measure of support for different edges
in a phylogeny [2].

In this paper we extend and complete the theorem of Allman and Rhodes and
derive an exact formula for the rank of arbitrary flattenings of a tree. Our
result corrects a formula appearing in [14]. We show that the rank of
$\mathrm{flat}_{A|B}$ is given by $r^{\ell_{T}(A|B)}$, where $\ell_{T}(A|B)$
is the parsimony length of the binary character which assigns one state to all
leaves in $A$ and another state to all leaves in $B$. A slightly modified
result holds for non-binary (multifurcating) trees.

In the next section we present the notation and basic results needed to
establish this result. We note that we generalise from characters to maps on
arbitrary subsets of vertices, and define our concepts in this more general
context. The main result is proved in a series of lemmas and propositions in
the final section.

Since completing this work, we have learnt that an equivalent result has been
proved much earlier by Casanellas and Fernández-Sánchez [11], using a
completely different proof strategy.

##  2 Background

###  2.1 Trees and characters

An unrooted phylogeny is an acyclic, connected graph $T=(V,E)$ with leaf set
(taxon set) $L(T)$. We say that $T$ is binary (full resolved) if every non-
leaf vertex has degree three. In a rooted phylogeny $T=(V,E_{\rho})$ one
vertex is selected as the root $\rho$ and edges are directed away from $\rho$.
The rooted phylogeny $T$ is binary if every non-leaf vertex has out-degree
$2$.

A character is a function $f$ from $L(T)$ to a set of states
$[r]=\\{1,2,\ldots,r\\}$. Hence $r=4$ for nucleotides and $r=20$ for amino
acids. We will consider a more general situation where $f$ is a map from any
subset of $V$ to $[r]$, not just the set $L(T)$.

The length of a function $F:V\rightarrow[r]$ is defined as

$\ell_{T}(F)=|\left\\{\\{u,v\\}\in E:F(u)\neq F(v)\right\\}|$

and the (parsimony) length a function $f$ with domain $A\subseteq V$ is the
length of a minimum extension

$\ell_{T}(f)=\min\\{\ell_{T}(F):F|_{A}=f\\}.$

The length of a function or character can be expressed equivalently using
vertex and edge cuts. For $E^{\prime}\subseteq E$ or $V^{\prime}\subseteq V$
we let $T\setminus E^{\prime}$ and $T\setminus V^{\prime}$ denote the graphs
resulting from deleting $E^{\prime}$ or $V^{\prime}$ respectively. The length
$\ell_{T}(f)$ equals the minimum cardinality of an edge cut
$E^{\prime}\subseteq E$ such that $f(u)=f(v)$ whenever $u$ and $v$ are in the
same component of $T\setminus E^{\prime}$. In a similar way, we let
$\nu_{T}(f)$ denote the minimum cardinality of a vertex cut
$V^{\prime}\subseteq V$ such that $f(u)=f(v)$ whenever $u$ and $v$ are in the
same component of $T\setminus V^{\prime}$. For all $f$ we have
$\nu_{T}(f)\leq\ell_{T}(f)$.

If $A$ and $B$ are disjoint subsets of $V$ then we let $\ell_{T}(A|B)$ and
$\nu_{T}(A|B)$ denote $\ell_{T}(f)$ and $\nu_{T}(f)$, where $f$ is the
function given by

$f(x)=\begin{cases}0&\mbox{ if $x\in A$}\\\ 1&\mbox{ if $x\in B$.}\end{cases}$

Steel [21, 19] observed that the parsimony length of a character with two
states can be expressed in terms of the size of disjoint path sets . This
applies for both $\ell_{T}(A|B)$ and $\nu_{T}(A|B)$.

######  Proposition 1.

Let $T=(V,E)$ be an unrooted phylogeny and let $A$ and $B$ be disjoint subsets
of $V$. Then $\ell_{T}(A|B)$ equals the maximum cardinality of a set of edge-
disjoint paths connecting vertices in $A$ with vertices in $B$, while
$\nu_{T}(A|B)$ equals the maximum cardinality of a set of vertex-disjoint
paths connecting vertices in $A$ with vertices in $B$.

######  Corollary 1.

Let $T=(V,E)$ be a binary phylogeny and suppose $A$ and $B$ are disjoint
subsets of $L(T)$. Then $\ell_{T}(A|B)=\nu_{T}(A|B)$.

###### Proof.

If $p_{1}$ and $p_{2}$ are any two paths in a binary phylogeny which begin and
end at leaves then $p_{1}$ and $p_{2}$ are vertex disjoint if and only if they
are edge disjoint. $\blacksquare$

###  2.2 Stochastic models on trees

The standard stochastic models on phylogenies determine the joint
probabilities for the states at every vertex of the tree. Let $T=(V,E_{\rho})$
be a rooted tree with root $\rho$. Let $\pi_{\rho}$ denote the root
distribution and for each directed edge $(u,v)$ we associate an $r\times r$
transition probability matrix $P_{uv}$. Let $X_{v}$ denote the random state
associated with vertex $v$ and, for $A\subseteq V$, let $X_{A}$ denote the
joint random variable $X_{a}:a\in A$.

The joint probability that $X_{v}=F(v)$ for all $v\in V$ is

$\pi(X_{V}=F)=\pi_{\rho}(F(\rho))\prod_{(u,v)\in E_{\rho}}P_{uv}(F(u),F(v)).$

The marginal probabilities for maps $f:A\rightarrow[r]$ on some subset
$A\subseteq V$ are then given by

$\pi(X_{A}=f)=\sum_{F:F|_{A}=f}\pi(F).$

With this notation, the standard probability for a character
$f:L(T)\rightarrow[r]$ is $\pi(X_{L(T)}=f)$.

We will make three assumptions about the parameters of the stochastic model.

  1. (C1)

The transition matrices $P_{uv}$ are non-singular.

  2. (C2)

$\pi_{\rho}(i)>0$ for all $i\in[r]$.

  3. (C3)

$P_{uv}(i,j)>0$ for all edges $(u,v)$ and $i,j\in[r]$.

We note that all three are satisfied in standard evolutionary models, where
mutations along a branch are modelled using continuous time Markov chains.

These conditions have three immediate consequences.

######  Proposition 2.

Suppose that conditions (C1) and (C2) are satisfied. Then

  1. 1.

$\pi(X_{v}=i)>0$ for all $v\in V$ and $i\in[r]$.

  2. 2.

For all $u,v\in V$ (not necessarily adjacent) the $r\times r$ matrix with
entries $P_{uv}=\pi(X_{v}=j|X_{u}=i)$ is non-singular.

  3. 3.

For all $u,v\in V$ the $r\times r$ matrix with entries
$M_{ij}=\pi(X_{u}=i,X_{v}=j)$ is non-singular.

###### Proof.

  1. 1.

See [20], Theorem 2.

  2. 2.

Let $v_{1},v_{2},\ldots,v_{k}$ be the path from $v_{1}=u$ to $v_{k}=v$. Then

$P_{uv}=P_{v_{1}v_{2}}P_{v_{2}v_{3}}\cdots P_{v_{k-1}v_{k}},$

which is non-singular by (C1).

  3. 3.

Let $\Pi_{u}$ be the diagonal matrix with entries $\pi(X_{u}=i)$ on the
diagonal. Then $M=\Pi P_{uv}$ so is non-singular by parts 1 and 2.

$\blacksquare$

For any edge $(u,v)$ in the rooted tree $T=(V,E_{\rho})$ we can define a
transition matrix $P_{vu}$ for the reverse edge $(v,u)$ using Bayes’ rule:

$\displaystyle P_{vu}(i,j)$ $\displaystyle=\pi(X_{u}=j|X_{v}=i)$
$\displaystyle=\pi(X_{v}=i|X_{u}=j)\frac{\pi(X_{u}=j)}{\pi(X_{v}=i)}$ (3)
$\displaystyle=P_{uv}(j,i)\frac{\pi(X_{u}=j)}{\pi(X_{v}=i)}.$

This formula allows us to move the root to any vertex in the tree with no
change to the distribution of joint random variables $X_{V}$ [4, 20]. To move
from the root from $\rho$ to $\hat{\rho}$ we make the new root distribution
$\pi_{\hat{\rho}}=\pi(X_{\hat{\rho}})$ and use (3) to determine transition
matrices for all edges which are flipped when directing away from $\hat{\rho}$
instead of from $\rho$ (under the assumption that (C1) and (C2) both hold).

Conditional independence for the variables $X_{v}$ are, as with any graphical
model, determined by cuts in the graph. More specifically, if
$A_{1},A_{2},\ldots,A_{k}$ are the components of $T\setminus\\{v\\}$ then
$X_{A_{1}},X_{A_{2}},\ldots,X_{A_{k}}$ are conditionally independent, given
$X_{v}$, see [22, Lemma 7.1]. The following Proposition is a direct
consequence of this result

######  Proposition 3.

If $V^{\prime}\subseteq V$ and $A_{1},A_{2},\ldots,A_{k}$ are the components
of $T\setminus\\{V^{\prime}\\}$ then $X_{A_{1}},X_{A_{2}},\ldots,X_{A_{k}}$
are conditionally independent, given $X_{V^{\prime}}$.

###### Proof.

Apply Lemma 7.1 of [22] with respect to some $v\in V^{\prime}$ and then apply
the result recursively on the components. $\blacksquare$

###  2.3 The main theorem

Let $T=(V,E)$ be a phylogeny and suppose that $A$ and $B$ are disjoint subsets
of $V$. We let $\mathrm{flat}_{A|B}$ denote the matrix with rows indexed by
maps $f_{A}:A\rightarrow[r]$, columns indexed by maps $f_{B}:B\rightarrow[r]$
and $(f_{A},f_{B})$ entry given by

$\mathrm{flat}_{A|B}(f_{A},f_{B})=\pi(X_{A}=f_{A},X_{B}=f_{B}).$

Hence $\mathrm{flat}_{A|B}$ is an $r^{|A|}\times r^{|B|}$ non-negative matrix
with entries which sum to $1$.

######  Theorem 1.

Let $T=(V,E)$ be a phylogeny and let $A$ and $B$ be disjoint subsets of $V$.
Suppose that the root distribution and transition matrices satisfy (C1)—(C3).
Then

$\mathrm{rank}(\mathrm{flat}_{A|B})=r^{\nu_{T}(A|B)}.$

If $T$ is binary and $A$ and $B$ subsets of $L(T)$ then

$\mathrm{rank}(\mathrm{flat}_{A|B})=r^{\ell_{T}(A|B)}.$

##  3 Proof of Theorem 1

We prove the main theorem in two steps. First, we show that $r^{\nu_{T}(A|B)}$
provides an upper bound for the rank of $\mathrm{flat}_{A|B}$; second we show
that this upper bound is actually achieved.

######  Lemma 1.

Let $T=(V,E)$ be a phylogeny and suppose that $A$ and $B$ are disjoint subsets
of $V$. Then

$\mathrm{rank}(\mathrm{flat}_{A|B})\leq r^{\nu_{T}(A|B)}.$

###### Proof.

Let $C$ be a minimum cardinality vertex cut of $T$ such that each component of
$T\setminus C$ contains vertices from at most one of $A$ or $B$. By
Proposition 3 $X_{A\setminus C}$ and $X_{B\setminus C}$ are conditionally
independent given $X_{C}$. Hence for all maps $f_{A}:A\rightarrow[r]$ and
$f_{B}:B\rightarrow[r]$ we can factor $\pi(X_{A}=f_{A},X_{B}=f_{B})$ as

$\displaystyle\pi(X_{A}=f_{A},X_{B}=f_{B})$
$\displaystyle=\sum_{f_{C}}\pi(X_{A}=f_{A},X_{B}=f_{B}|X_{C}=f_{C})\pi(X_{C}=f_{C})$
$\displaystyle=\sum_{f_{C}}\pi(X_{A}=f_{A}|X_{C}=f_{C})\pi(X_{B}=f_{B},X_{C}=f_{C})$

Define the $r^{|A|}\times r^{|C|}$ matrix $R$ by

$R(f_{A},f_{C})=\pi(X_{A}=f_{A}|X_{C}=f_{C}),$

and the $r^{|C|}\times r^{|B|}$ matrix $S$ by

$S(f_{C},f_{B})=\pi(X_{B}=f_{B},X_{C}=f_{C}).$

Then

$\mathrm{flat}_{A|B}=RS$

and

$\mathrm{rank}(\mathrm{flat}_{A|B})\leq\mathrm{rank}(R)\leq
r^{|C|}=r^{\nu_{T}(A|B)}.$

$\blacksquare$

To illustrate, consider the tree in figure 2. The sets $A$ and $B$ are
indicated by filled and unfilled leaves respectively. Removing the three
marked vertices separates all leaves in $A$ from leaves in $B$. Hence
$\nu_{T}(A|B)\leq 3$ and $\mathrm{rank}(\mathrm{flat}_{A|B})\leq
r^{\nu_{T}(A|B)}$. We note that the formula in [14] gives a generic rank of
$r^{4}$ for this flattening.

Figure 2:  A counter-example for the rank formula in [14]. Let $A$ and $B$ be
given by the filled and unfilled leaf nodes, respectively. The three squares
mark out a vertex cut of size $3$ separating $A$ from $B$. Hence the rank of
$\mathrm{flat}_{A|B}$ is at most $r^{3}$, for $r$ states. Theorem 19.5 of [14]
states that the generic rank is $r^{4}$.

The second part of the proof of the main theorem is proving a matching lower
bound for Lemma 1. We start by demonstrating that the rank of
$\mathrm{flat}_{A|B}$ increases monotonically as a function of $A$ and $B$.

######  Lemma 2.

Let $A$ and $B$ be disjoint subsets of $V$ and suppose $A^{\prime}\subseteq A$
and $B^{\prime}\subseteq B$. Then

$\mathrm{rank}(\mathrm{flat}_{A^{\prime}|B^{\prime}})\leq\mathrm{rank}(\mathrm{flat}_{A|B}).$

###### Proof.

For any $f_{A^{\prime}}:A^{\prime}\rightarrow[r]$ and
$f_{B^{\prime}}:B^{\prime}\rightarrow[r]$ we have

$\displaystyle\mathrm{flat}_{A^{\prime}|B^{\prime}}(f_{A^{\prime}},f_{B^{\prime}})$
$\displaystyle=\pi(X_{A^{\prime}}=f_{A^{\prime}},X_{B^{\prime}}=f_{B^{\prime}})$
$\displaystyle=\sum_{\begin{subarray}{c}g_{A}:A\rightarrow[r]\\\
g_{A}|_{A^{\prime}}=f_{A^{\prime}}\end{subarray}}\sum_{\begin{subarray}{c}g_{B}:B\rightarrow[r]\\\
g_{B}|_{B^{\prime}}=f_{B^{\prime}}\end{subarray}}\pi(X_{A}=g_{A},X_{B}=g_{B})$
$\displaystyle=\sum_{\begin{subarray}{c}g_{A}:A\rightarrow[r]\\\
g_{A}|_{A^{\prime}}=f_{A^{\prime}}\end{subarray}}\sum_{\begin{subarray}{c}g_{B}:B\rightarrow[r]\\\
g_{B}|_{B^{\prime}}=f_{B^{\prime}}\end{subarray}}\mathrm{flat}_{A|B}(g_{A},g_{B}).$

Hence there is an $r^{|A^{\prime}|}\times r^{|A|}$ $0\\!-\\!1$ (binary) matrix
$U_{A}$ and a $r^{|B^{\prime}|}\times r^{|B|}$ $0\\!-\\!1$ matrix $U_{B}$ such
that

$\mathrm{flat}_{A^{\prime}|B^{\prime}}=U_{A}\mathrm{flat}_{A|B}U_{B}^{T}$

and
$\mathrm{rank}(\mathrm{flat}_{A^{\prime}|B^{\prime}})\leq\mathrm{rank}(\mathrm{flat}_{A|B})$.
$\blacksquare$

The next Lemma establishes Theorem 1 in the extremal case that
$\nu_{T}(A|B)=|A|=|B|$. This is where the bulk of the work proving the main
theorem is carried out.

######  Lemma 3.

Suppose that $T=(V,E)$, $A$ and $B$ satisfy the conditions of Theorem 1. If
$|A|=|B|=m$ and there are $m$ disjoint paths connecting elements of $A$ to
elements of $B$ then $\mathrm{rank}(\mathrm{flat}_{A|B})=r^{m}$.

###### Proof.

We prove the result by induction on $m$.

For the base case suppose that $m=1$, $A=\\{a\\}$ and $B=\\{b\\}$. Then

$\mathrm{flat}_{A|B}(i,j)=\pi(X_{a}=i,X_{B}=j)$

which is full rank $r=r^{\nu_{T}(A|B)}$ by Proposition 2.

Next, assume that the result holds when $|A|=|B|=m$. Suppose that there is a
collection of $m+1$ vertex disjoint paths connecting elements of $A^{\prime}$
and $B^{\prime}$, where $|A^{\prime}|=|B^{\prime}|=m+1$. Fix a vertex $\rho\in
V$ and let $p$ be the path furthest away from $\rho$. Suppose that this path
goes from $a\in A^{\prime}$ to $b\in B^{\prime}$. Let $v\in p$ be the vertex
on $p$ closest to $\rho$ and let $e=\\{v,w\\}$ be the first edge on the path
from $v$ to $\rho$. If there is a path $p^{\prime}$ in the same component of
$T\setminus\\{e\\}$ then $v$ is on the path from $p^{\prime}$ to $\rho$,
contradicting the choice of $p$.

Let $A=A^{\prime}\setminus\\{a\\}$ and $B=B^{\prime}\setminus\\{b\\}$. Define
the matrices $F,G$ by

$\displaystyle F(i,k)$ $\displaystyle=\pi(X_{a}=i|X_{v}=k)$ $\displaystyle
G(k,j)$ $\displaystyle=\pi(X_{v}=k,X_{b}=j)$ and for each $k\in[n]$ define the
$r^{m}\times r^{m}$ matrix $\displaystyle H^{(k)}(f,g)$
$\displaystyle=\pi(X_{A}=f,X_{B}=g|X_{v}=k).$

Note that $F$ and $G$ are both non-singular, by Lemma 2. Furthermore, for each
$k$ the matrix $H^{(k)}$ equals the flattening matrix $\mathrm{flat}_{A|B}$
but with respect to root $\rho=w$ and root distribution

$\pi_{\rho}(i)=P_{vw}(k,i).$

Hence by the induction hypothesis, $H^{(k)}$ also has full rank.

Suppose that $\hat{f}:\hat{A}\rightarrow[r]$ and
$\hat{g}:\hat{B}\rightarrow[r]$. Let $i=\hat{f}(a)$, $j=\hat{g}(b)$ and let
$f,g$ be the restrictions of $\hat{f}$ and $\hat{g}$ to $A$ and $B$. Then

$\displaystyle\mathrm{flat}_{\hat{A}|\hat{B}}(\hat{f},\hat{g})$
$\displaystyle=\sum_{k=1}^{r}F(i,k)H^{(k)}(f,g)G(k,j).$

We will suppose that the null space of
$\mathrm{flat}_{\hat{A}|\hat{B}}(\hat{f},\hat{g})$ contains no non-zero
vectors. To this end, let $x$ be a vector indexed by pairs $(g,j)$ with
$g:B\rightarrow[r]$ and $j\in[r]$ such that

$\displaystyle\sum_{g}\sum_{j=1}^{r}\sum_{k=1}^{r}F(i,k)H^{(k)}(f,g)G(k,j)x(g,j)$
$\displaystyle=0$ for all $f:A\rightarrow[r]$ and $i\in[r]$. Rearranging, we
have
$\displaystyle\sum_{k=1}^{r}F(i,k)\left[\sum_{g}\sum_{j=1}^{r}H^{(k)}(f,g)G(k,j)x(g,j)\right]$
$\displaystyle=0$ and since $F$ is non-singular,
$\displaystyle\sum_{g}\sum_{j=1}^{r}H^{(k)}(f,g)G(k,j)x(g,j)$
$\displaystyle=0$

for all $f$ and $k$. Define the vector $y$ by

$y(g,k)=\sum_{j=1}^{r}G(k,j)x(g,j)$ (4)

so that for all $k$,

$\displaystyle\sum_{g}H^{(k)}(f,g)y(g,k)$ $\displaystyle=0.$

As $H^{(k)}$ is non-singular, $y(g,k)=0$ for all $g,k$, from which (4) and the
fact that $G$ is non-singular gives $x=0$. We have shown that the null space
of $\mathrm{flat}_{\hat{A}|\hat{B}}$ is trivial, proving the lemma.
$\blacksquare$

We can now prove the main theorem.

###### Proof.

(Theorem 1) Suppose that $A$ and $B$ are disjoint subsets of $V$. From Lemma 1
we have

$\mathrm{rank}(\mathrm{flat}_{A|B})\leq r^{\nu_{T}(A|B)}.$

By Proposition 1 there are $\nu_{T}(A|B)$ vertex disjoint paths connecting
vertices in $A$ to vertices in $B$. Let $A^{\prime}$ and $B^{\prime}$ be the
endpoints of these paths, so
$|A^{\prime}|=|B^{\prime}|=\nu_{T}(A^{\prime}|B^{\prime})=\nu_{T}(A|B)$. By
Lemma 3 we have
$\mathrm{rank}(\mathrm{flat}_{A^{\prime}|B^{\prime}})=r^{\nu_{T}(A|B)}$ and by
Lemma 2 we have

$\mathrm{rank}(\mathrm{flat}_{A|B})\geq\mathrm{rank}(\mathrm{flat}_{A^{\prime}|B^{\prime}})=r^{\nu_{T}(A|B)}.$

The second part of the theorem now follows from Corollary 1. $\blacksquare$

We note that none of the conditions (C1)—(C3) on the root distribution and
transition matrices can be eliminated. For example, consider the four taxa
tree in Figure 1, a case studied in detail by [5]. The joint probability
distribution for $X_{1},X_{2},X_{3},X_{4}$ is

$\pi(X_{1}=a,X_{2}=b,X_{3}=c,X_{4}=d)=\sum_{i}\sum_{j}P_{u1}(i,a)P_{u2}(i,b)\pi_{\rho}(i)P_{uv}(i,j)P_{v3}(j,c)P_{v4}(j,d).$

Gather terms, we obtain a decomposition

$\mathrm{flat}_{\\{1,3\\}|\\{2,4\\}}=UDV$

where $U$ and $V$ are $r^{2}\times r^{2}$ matrices and $D$ is a diagonal
matrix with diagonal entries

$D_{ij;ij}=\pi_{\rho}(i)P_{uv}(i,j).$

From here we see that if there is $i$ such that $\pi_{\rho}(i)=0$, or $ij$
such that $P_{uv}(i,j)=0$, then

$\mathrm{rank}(\mathrm{flat}_{\\{1,3\\}|\\{2,4\\}})<r^{2}.$

## References

  * [1] Elizabeth S Allman, Peter D Jarvis, John A Rhodes, and Jeremy G Sumner.  Tensor rank, invariants, inequalities, and applications.  SIAM Journal on Matrix Analysis and Applications, 34(3):1014–1045, 2013.
  * [2] Elizabeth S. Allman, Laura S. Kubatko, and John A. Rhodes.  Split Scores: A Tool to Quantify Phylogenetic Signal in Genome-Scale Data.  Systematic Biology, 66(4):620–636, 01 2017.
  * [3] Elizabeth S Allman and Rhodes.  Phylogenetic invariants.  Mathematics of evolution and phylogeny. Oxford University Press, Oxford, UK, pages 108–146, 2005.
  * [4] Elizabeth S Allman and John A Rhodes.  Phylogenetic invariants for the general markov model of sequence mutation.  Mathematical biosciences, 186(2):113–144, 2003.
  * [5] Elizabeth S Allman and John A Rhodes.  The identifiability of tree topology for phylogenetic models, including covarion and mixture models.  Journal of Computational Biology, 13(5):1101–1113, 2006.
  * [6] Elizabeth S Allman and John A Rhodes.  Identifying evolutionary trees and substitution parameters for the general Markov model with invariable sites.  Mathematical Biosciences, 211(1):18–33, 2007.
  * [7] Elizabeth S Allman and John A Rhodes.  Phylogenetic ideals and varieties for the general Markov model.  Advances in Applied Mathematics, 40(2):127–148, 2008.
  * [8] Elizabeth S Allman and John A Rhodes.  The identifiability of covarion models in phylogenetics.  IEEE/ACM transactions on computational biology and bioinformatics, 6(1):76–88, 2009.
  * [9] Elizabeth S Allman, John A Rhodes, and Amelia Taylor.  A semialgebraic description of the general Markov model on phylogenetic trees.  SIAM Journal on Discrete Mathematics, 28(2):736–755, 2014.
  * [10] David Bryant, Nicolas Galtier, and Marie-Anne Poursat.  Likelihood calculation in molecular phylogenetics.  Mathematics of evolution and phylogeny. Oxford University Press, Oxford, UK, pages 33–62, 2005.
  * [11] Marta Casanellas and Jesús Fernández-Sánchez.  Relevant phylogenetic invariants of evolutionary models.  Journal de Mathématiques Pures et Appliquées, 96(3):207–229, 2011.
  * [12] Marta Casanellas, Jesús Fernández-Sánchez, and Marina Garrote-López.  Saq: semi-algebraic quartet reconstruction.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2021.
  * [13] Julia Chifman and Laura Kubatko.  Quartet inference from snp data under the coalescent model.  Bioinformatics, 30(23):3317–3324, 2014.
  * [14] Nicholas Eriksson.  Tree construction using singular value decomposition.  In L. Pachter and B.Editors Sturmfels, editors, Algebraic Statistics for Computational Biology, pages 347–358. Cambridge University Press, 2005.
  * [15] Joseph Felsenstein.  Inferring phylogenies, volume 2.  Sinauer associates Sunderland, MA, 2004.
  * [16] Jesús Fernández-Sánchez and Marta Casanellas.  Invariant versus classical quartet inference when evolution is heterogeneous across sites and lineages.  Systematic biology, 65(2):280–291, 2016.
  * [17] Lior Pachter and Bernd Sturmfels.  Tropical geometry of statistical models.  Proceedings of the National Academy of Sciences, 101(46):16132–16137, 2004.
  * [18] John A Rhodes and Seth Sullivant.  Identifiability of large phylogenetic mixture models.  Bulletin of mathematical biology, 74(1):212–231, 2012.
  * [19] Charles Semple, Mike Steel, et al.  Phylogenetics, volume 24.  Oxford University Press on Demand, 2003.
  * [20] M A Steel, L A Székely, and M D Hendy.  Reconstructing Trees When Sequence Sites Evolve at Variable Rates.  Journal of Computational Biology, 1(2):153–163, 1994.
  * [21] Michael A Steel.  Distributions on bicoloured binary trees arising from the principle of parsimony.  Discrete applied mathematics, 41(3):245–261, 1993.
  * [22] Mike Steel.  Phylogeny: discrete and random processes in evolution.  SIAM, 2016.