Parsimony and the rank of a flattening matrix

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 [Formula: see text], where r is the number of states and [Formula: see text] is the minimum size of a vertex cut separating A from B. When T is binary the rank of the flattening equals [Formula: see text] where [Formula: see text] equals the parsimony length of the binary character separating A and B. We provide a direct proof that requires little more than undergraduate algebra, but note that the formula could also be derived from work by Casanellas and Fernández-Sánchez (2011) on phylogenetic invariants.

Keywords: Markov models on trees; Phylogenetic invariants; Phylogeny; Rank formula; Tensor flattening.