A Spectral Algorithm for Seriation and the Consecutive Ones Problem.
In applications ranging from DNA sequencing through archeological dating to sparse matrix reordering, a recurrent problem is the sequencing of elements in such a way that highly correlated pairs of elements are near each other.  That is, given a correlation function f reflecting the desire for each pair of elements to be near each other, find all permutations $\pi$ with the property that if $\pi(i)<\pi(j)<\pi(k)$ then $f(i,j) \ge f(i,k)$ and $f(j,k) \ge f(i,k)$. This seriation problem is a generalization of the well-studied consecutive ones problem.  We present a spectral algorithm for this problem that has a number of interesting features. Whereas most previous applications of spectral techniques provide only bounds or heuristics, our result is an algorithm that correctly solves a nontrivial combinatorial problem. In addition, spectral methods are being successfully applied as heuristics to a variety of sequencing problems, and our result helps explain and justify these applications.
Introduction
. Many applied computational problems involve ordering a set
so that closely coupled elements are placed near each other. This is the underlying
problem in such diverse applications as genomic sequencing, sparse matrix envelope
reduction and graph linear arrangement as well as less familiar settings such as archaeological
dating. In this paper we present a spectral algorithm for this class of
problems. Unlike traditional combinatorial methods, our approach uses an eigenvector
of a matrix to order the elements. Our main result is that this approach correctly
solves an important ordering problem we call the seriation problem which includes the
well known consecutive ones problem [5] as a special case.
More formally, we are given a set of n elements to sequence; that is, we wish to
bijectively map the elements to the integers We also have a symmetric, real
valued correlation function (sometimes called a similarity function) that reflects the
desire for elements to be near each other in the sequence. We now wish to
find all ways to sequence the elements so that the correlations are consistent; that is,
if - is our permutation of elements
k). Although there may be an exponential number of such orderings,
they can all be described in a compact data structure known as a PQ-tree [5] which
we review in the next section. Not all correlation functions allow for a consistent
sequencing. If a consistent ordering is possible we will say the problem is well posed.
Determining an ordering from a correlation function is what we will call the seriation
problem, reflecting its origins in archaeology [29, 33].
This work was supported by the Mathematical, Information and Computational Sciences Division
of the U.S. DOE, Office of Energy Research, and work at Sandia National Laboratories, operated for
the U.S. DOE under contract No. DE-AC04-94AL85000. Sandia is multiprogram laboratory operated
by Sandia Corporation, a Lockheed Martin Company, for the U.S. DOE.
y Dept. Mathematics, University of Michigan, 2072 East Hall, Ann Arbor, MI 48109.
atkinsje@math.lsa.umich.edu.
z Scientific Computing & Computational Mathematics, Gates Bldg. 2B, Stanford Univ., Stanford,
94305-9025. boman@sccm.stanford.edu.
x Applied & Numerical Mathematics Dept., Sandia National Labs, Albuquerque, NM 87185-1110.
bah@cs.sandia.gov.
The consecutive ones problem (C1P) is a closely related ordering problem. A
1)-matrix C has the consecutive ones property if there exists a permutation matrix
\Pi such that for each column in \PiC, all the ones form a consecutive sequence. If a
matrix has the consecutive ones property, then the consecutive ones problem is to find
all such permutations. As shown by Kendall [19] and reviewed in x6, C1P is a special
case of the seriation problem.
Our algorithm orders elements using their value in an eigenvector of a Laplacian
matrix which we formally define in x2. Eigenvectors related to graphs have been studied
since the 1950's (see, for example, the survey books by Cvetkovi'c et al. [8, 7]. Most
of the early work involved eigenvectors of adjacency matrices. Laplacian eigenvectors
were first studied by Fiedler [10, 11] and independently by Donath and Hoffman [9].
More recently, there have been a number of attempts to apply spectral graph theory
to problems in combinatorial optimization. For example, spectral algorithms have
been developed for graph coloring [3], graph partitioning [9, 28] and envelope reduction
[4], and more examples can be found in the survey papers of Mohar [23, 24].
However, in most previous applications, these techniques have been used to provide
bounds, heuristics, or in a few cases, approximation algorithms [2, 6, 14] for NP-hard
problems. There are only a small number of previous results in which eigenvector
techniques have been used to exactly solve combinatorial problems including finding
the number of connected components of a graph [10], coloring k-partite graphs [3],
and finding stable sets (independent sets) in perfect graphs [16]. This paper describes
another such application.
Spectral methods are closely related to the more general method of semidefinite
programming, which has been applied successfully to many combinatorial problems
(e.g. MAX-CUT and MAX-2SAT[14] and graph coloring[18]). See Alizadeh[1] for a
survey of semidefinite programming with applications to combinatorial optimization.
Our result is important for several reasons. First, it provides new insight into the
well-studied consecutive ones problem. Second, some important practical problems
like envelope reduction for matrices and genomic reconstruction can be thought of
as variations on seriation. For example, if biological experiments were error-free, the
genomic reconstruction problem would be precisely C1P. Unfortunately, real experimental
data always contain errors, and attempts to generalize the consecutive ones
concept to data with errors seems to invariably lead to NP-complete problems [31, 15].
A spectral heuristic based upon our approach has recently been applied to such problems
and found to be highly successful in practice [15]. Our result helps explain this
empirical success by revealing that in the error-free case the technique will correctly
solve the problem. This places the spectral method on a stronger theoretical footing
as a cross between a heuristic and an exact algorithm. Similar comments apply to
envelope reduction. Matrices with dense envelopes are closely related to matrices with
the consecutive ones property. Recent work has shown spectral techniques to be better
in practice than any existing combinatorial approaches at reducing envelopes [4]. Our
result sheds some light on this success.
Another way to interpret our result is that we provide an algorithm for C1P that
generalizes to become an attractive heuristic in the presence of errors. Designed as decision
algorithms for the consecutive ones property, existing combinatorial approaches
for C1P break down if there are errors and fail to provide useful approximate orderings.
However, our goal here is not to analyze the approach as an approximation algorithm,
but rather to prove that it correctly solves error-free problem instances.
This paper is organized in the following way. In the next section we introduce the
mathematical notation and the results from matrix theory that we will need later. We
also describe a spectral heuristic for ordering problems which motivates the remainder
of the paper. The theorem that underpins our algorithm is proved in x3, the proof of
which requires the use of a classic theorem from matrix analysis. Several additional
results in x4 lead us to an algorithm and its analysis in x5. We review the connection
to C1P in x6.
2. Mathematical background.
2.1. Notation and Definitions. Matrix concepts are useful because the correlation
function defined above can be considered as a real, symmetric matrix. A
permutation of the elements corresponds to a symmetric permutation of this matrix,
a permutation of the matrix elements formed by permuting the rows and the columns
in the same fashion. The question of whether or not the ordering problem is well
posed can also be asked as a property of this matrix. Specifically, suppose the matrix
has been permuted to reflect a consistent solution to the ordering problem. The
off-diagonal matrix entries must now be non-increasing as we move away from the
diagonal. More formally, we will say a matrix A is an R-matrix 1 if and only if A is
symmetric and
a i;j - a i;k for
a i;j - a i;k for
The diagonal entries of an R-matrix are unspecified. If A can be symmetrically permuted
to become an R-matrix, then we say that A is pre-R. Note that pre-R matrices
correspond precisely to well-posed ordering problems. Also, the R-matrix property is
preserved if we add a constant to all off-diagonal entries, so we can assume without
loss of generality that all off-diagonal values are non-negative.
When - is a permutation of the natural numbers ng and x is a column
vector, i.e. we will denote by x - the permutation of x by -, i.e.
Similarly, A - is the symmetric permutation of A by -, i.e. a -
We denote by e the vector whose entries are all 1, by e i the vector consisting of zeros
except for a 1 in position i, and by I the identity matrix. A symmetric matrix A is
reducible if there exists a permutation - such that
where B and C are non-empty square matrices. If no such permutation exists then
A is irreducible. If B and C are themselves irreducible, then we refer to them as the
irreducible blocks of A.
We say that - is an eigenvalue of A if
corresponding vector x is an eigenvector. An n \Theta n real, symmetric matrix has n
eigenvectors that can be constructed to be pairwise orthogonal, and its eigenvalues
are all real. We will assume that the eigenvalues are sorted by increasing value, and
refer to them as - i , n. The (algebraic) multiplicity of an eigenvalue - is
This class of matrices is named after W. S. Robinson who first defined this property in his work
on seriation methods in archaeology [29].
defined as the number of times - occurs as a root in the characteristic polynomial
value that occurs only once is called simple; the eigenvector
of a simple eigenvalue is unique (up to normalization). We write A - 0 and say A is
non-negative if all its elements a i;j are non-negative. A real vector x is monotone if
We define the Laplacian of a symmetric matrix A to be
a diagonal matrix with d
a i;j . The minimum eigenvalue with an eigenvector
orthogonal to e (the vector of all ones) is called the Fiedler value and a corresponding
eigenvector is called a Fiedler vector 2 . Alternatively, the Fiedler value is given by
min
and a Fiedler vector is any vector x that achieves this minimum while satisfying these
constraints. When A - 0 and irreducible, it is not hard to show that the Fiedler
value is the smallest non-zero eigenvalue and a Fiedler vector is any corresponding
eigenvector. We will be notationally cavalier and refer to the Fiedler value and vector
of A when we really mean those of LA .
2.2. PQ-trees. A PQ-tree is a data structure introduced by Booth and Lueker
to efficiently encode a set of related permutations [5]. A PQ-tree over a set
is a rooted, ordered tree whose leaves are elements of U and whose
internal nodes are distinguished as either P-nodes or Q-nodes. A PQ-tree is proper
when the following three conditions hold:
1. Every element u appears precisely once as a leaf.
2. Every P-node has at least two children.
3. Every Q-node has at least three children.
Two PQ-trees are said to be equivalent if one can be transformed into the other by
applying a sequence of the following two equivalence transformations:
1. Arbitrarily permute the children of a P-node.
2. Reverse the children of a Q-node.
Conveniently, the equivalence class represented by a PQ-tree corresponds precisely to
the set of permutations consistent with an instance of a seriation problem. In x5 we
describe an algorithm which uses Laplacian eigenvectors to construct a PQ-tree for an
instance of the seriation problem.
2.3. Motivation for Spectral Methods. With the above definitions we can
describe a simple heuristic for the seriation problem that will motivate the remainder
of the paper. This heuristic is at the heart of the more complex algorithms we will
devise, and underlies many previous applications of spectral algorithms [17]. We begin
by constructing a simple penalty function g whose value will be small when closely
correlated elements are close to each other. We define
Unfortunately, minimizing g is NP-hard due to the discrete nature of the permutation
[13]. Instead we approximate it by a function h of continuous variables x i
that we can minimize and that maintains much of the structure of g. We define
. Note that h does not have a unique minimizer, since
its value does not change if we add a constant to each x component. To avoid this
ambiguity, we need to add a constraint like
We still have a trivial solution
2 This is in recognition of the work of Miroslav Fiedler [10, 11].
when all the x i 's are zero, so we need a second constraint like
1. The resulting
minimization problem is now well defined.
Minimize
(1)
subject to:
The solution to this continuous problem can be used as a heuristic for sequencing.
Merely construct the solution vector x, sort the elements x i and sequence based upon
their sorted order. One reason this heuristic is attractive is that the minimization
problem has an elegant solution. We can rewrite h(x) as x T L F x where is
the correlation matrix. The constraints require that x be a unit vector orthogonal to e,
and since LA is symmetric, all other eigenvectors satisfy the constraints. Consequently,
a solution to the constrained minimization problem is just a Fiedler vector.
Even if the problem is not well posed, sorting the entries of the Fiedler vector
generates an ordering that tries to keep highly correlated elements near each other. As
mentioned above, this technique is being used for a variety of sequencing problems [4,
15, 17]. The algorithm we describe in the remainder of the paper is based upon this
idea. However, when we encounter ties in entries of the Fiedler vector, we need to
recurse on the subproblem encompassing the tied values. In this way, we are able to
find all permutations which make a pre-R matrix into an R matrix.
3. The key theorem. Our main result is that a modification of the simple
heuristic presented in x2.3 is actually an algorithm for well-posed instances of the
seriation problem. Completely proving this will require us to deal with the special
cases of multiple Fiedler vectors and ties within the Fiedler vector. The cornerstone
of our analysis is a classical result in matrix theory due to Perron and Frobenius [27].
The particular formulation below can be found on page 46 of [30].
Theorem 3.1 (Perron-Frobenius). Let M be a real, non-negative matrix. If
we define
1. ae(M) is an eigenvalue of M , and
2. there is a vector x - 0 such that
We are now ready to state and prove our main theorem.
Theorem 3.2. If A is an R-matrix then it has a monotone Fiedler vector.
Proof. Our proof uses the Perron-Frobenius Theorem 3.1. The non-negative vector
in that theorem will consist of differences between neighboring entries in the Fiedler
vector of the Laplacian of A.
First define the matrix S 2 IR (n\Gamma1)\Thetan as
. 0
Note that for any vector x,
. 0
It is easy to verify that
1 . We define
g. We now show that Sx is an eigenvector of MA if
and only if x is an eigenvector of LA and x 6= ffe.
The transformation from the second to the third line follows from LA
holds between all the above equations, so - is an eigenvalue for both LA and
MA for eigenvectors of LA other than e. Hence the eigenvalues of MA are the same as
the eigenvalues of LA with the zero eigenvalue removed, and the eigenvectors of MA
are differences between neighboring entries of the corresponding eigenvectors of LA .
It is easily seen that (SLA )
(a i;k \gamma a i+1;k
Since, by assumption, A is an R-matrix, a i;k - a i+1;k for
j. For i ? j we can use the fact that
(l i;k \gamma l i+1;k
Again, from the R-matrix property we conclude that Consequently,
all the off-diagonal elements in MA are non-positive.
Now let fi be a value greater than are the eigenvalues of
MA . Then ~
non-negative with eigenvalues ~
MA and
MA share the same set of eigenvectors. By Theorem 3.1, there exists a non-negative
eigenvector y of ~
MA corresponding to the largest eigenvalue of ~
MA . But y is also an
eigenvector of MA corresponding to MA 's smallest eigenvalue. And this is just Sx,
where x is a Fiedler vector of LA . Since non-negative, the corresponding
Fiedler vector of LA is non-decreasing and the theorem follows. (Note that since the
sign of an eigenvector is unspecified, the Fiedler vector could also be non-increasing.)
Theorem 3.3. Let A be a pre-R matrix with a simple Fiedler value and a Fiedler
vector with no repeated values. Let - 1 (respectively - 2 ) be the permutation induced by
sorting the values in the Fiedler vector in increasing (decreasing) order. Then A - 1
and A - 2 are R-matrices, and no other permutations of A produce R-matrices.
Proof. First note that since the Fiedler value is simple, the Fiedler vector is unique
up to a multiplicative constant. Next observe that if x is the Fiedler vector of A, then
x - is the Fiedler vector of A - . So applying a permutation to A merely changes the
order of the entries in the Fiedler vector. Now let -   be a permutation such that A -
is an R-matrix. By Theorem 3.2 x -   is monotone since x is the only Fiedler vector.
Since x has no repeated values, -   must be either - 1 or - 2 .
Theorem 3.3 provides the essence of our algorithm for the seriation problem, but
it is too restrictive as the Fiedler value must be simple and contain no repeated values.
We will show how to remove these limitations in the next section.
4. Removing the restrictions. Several observations about the seriation problem
will simplify our analysis. First note that if we add a constant to all the correlation
values the set of solutions is unchanged. Consequently, we can assume without loss
of generality that the smallest value of the correlation function is zero. Note that
subtracting the smallest value from all correlation values does not change whether or
not the matrix is pre-R. In our algebraic formulation this translates into the following.
Lemma 4.1. Let A be a symmetric matrix and let -
real
ff. A vector x is a Fiedler vector of A iff x is a Fiedler vector of -
A. So without loss
of generality we can assume that the smallest off-diagonal entry of A is zero.
Proof. By the definition of a Laplacian it follows that L -
where n is the dimension of A. Then L -
but for any other eigenvector x of LA ,
That is, the eigenvalues are simply shifted down by ffn while
the eigenvectors are preserved.
This will justify the first step of our algorithm, which subtracts the value of the
smallest correlation from every correlation. Accordingly, we now make the assumption
that our pre-R matrix has smallest off diagonal entry of zero. Next observe that if A is
reducible then the seriation problem can be decoupled. The irreducible blocks of the
matrix correspond to connected components in the graph of the nonzero values of the
correlation function. We can solve the subproblems induced by each of these connected
components, and link the pieces together in an arbitrary order. More formally, we have
the following lemma.
Lemma 4.2. Let A i , be the irreducible blocks of a pre-R matrix A, and
let - i be a permutation of block A i such that the submatrix A - i
i is an R-matrix. Then
any permutation formed by concatenating the - i 's will make A become an R-matrix.
In terms of a PQ-tree, the - i permutations are children of a single P-node.
Proof. By Lemma 4.1, we can assume all entries in the irreducible blocks are non-
negative. Consequently, the correlation between elements within a block will always
be at least as strong as the correlation between elements in different blocks. Also, by
the definition of irreducibility, each element within a block must have some positive
correlation with another element in that block. Hence, any ordering that makes A i an
R-matrix must not interleave elements between different irreducible blocks. As long as
the blocks themselves are ordered to be R-matrices, any ordering of blocks will make
A an R-matrix since correlations across blocks are all identical.
With these preliminaries, we will now assume that the smallest off-diagonal value
is zero and that the matrix is irreducible. As the following three lemmas and theorem
show, this is sufficient to ensure that the Fiedler vector is unique up to a multiplicative
constant.
Lemma 4.3. Let A be an n \Theta n R-matrix with a monotone Fiedler vector x. If
is a maximal interval such that x
Proof. We can without loss of generality assume x is non-decreasing since \Gammax is
also a Fiedler vector. We will show that a r;k = a s;k for all
since A is an
R-matrix then all elements between a r;k and a s;k must also be equal. Consider rows r
and s in the equation
(l s;k \gamma l r;k )x
Since LA is a Laplacian, we know that
(l sk \gamma l rk )(x r \gamma x k )
(l s;k \gamma l r;k )
(l s;k \gamma l r;k )
where we have used the fact that x is non-decreasing. Because all terms in the sum
are non-negative, all terms must be exactly zero. By assumption, x k 6= x r for
and consequently l
2 J and the result follows.
The following lemma is essentially a converse of this. Its proof requires detailed
algebra, but it is not fundamental to what follows. Consequently, the proof is relegated
to the end of this section.
Lemma 4.4. Let A be an irreducible n \Theta n R-matrix with a
[1; n] is an interval such that a r;k = a s;k for all
any Fiedler vector x.
Lemma 4.5. Let A be an irreducible R-matrix with a
Fiedler vector of A. If is an interval such that x
for any Fiedler vector y, y
Proof. First apply Lemma 4.3 to conclude that for any k =
Now use this in conjunction with
Lemma 4.4 to obtain the result.
Theorem 4.6. If A is an irreducible R-matrix with a then the Fiedler
value - 2 is a simple eigenvalue.
Proof. We will assume that - 2 is a repeated eigenvalue and produce a contradic-
tion. Let x and y be two linearly independent Fiedler vectors with x non-decreasing.
sin(')y, with 0 -. Let '   be the smallest value of '
that makes z Such a '   must exist since x and
y are linearly independent.
By Lemma 4.5 the indices of any repeated values in x are indices of repeated
values in y and z('). Coupled with the monotonicity of x, this implies that z('   ) is
monotone. By Lemma 4.5 the indices of any repeated values in z('   ) must be repeated
in x which gives the desired contradiction.
All that remains is to handle the situation where the Fiedler vector has repeated
values. As the following theorem shows, repeated values decouple the problem into
pieces that can be solved recursively.
Theorem 4.7. Let A be a pre-R matrix with a simple Fiedler value and Fiedler
vector x. Suppose there is some repeated value fi in x and define I, J and K to be
the indices for which
1.
2. x
3.
Then - is an R-matrix ordering for A iff - or its reversal can be expressed as (-
is an R-matrix ordering for the submatrix A(J ; J ) of A induced by J , and - i
and - k are the restrictions of some R-matrix ordering for A to I and K, respectively.
Proof. From Theorem 3.2 we know that for any R-matrix ordering A - , x - is
monotone, so elements in I must appear before (after) elements from J and elements
from K must appear after (before) elements from J . By Lemma 4.3, we have a
for all
2 J . Hence the orderings of elements inside J must be indifferent
to the ordering outside of J and vice versa. Consequently, the R-matrix ordering of
elements in J depends only of A(J ; J ).
Algorithmically, this theorem means that we can break ties in the Fiedler vector
by recursing on the submatrix A(J ; J ) where J corresponds to the set of repeated
values. The distinct values in the Fiedler vector of A constrain R-matrix orderings,
but repeated values need to be handled recursively. In the language of PQ-trees,
the distinct values are combined via a Q-node, and the components (subtrees) of the
Q-node must then be expanded recursively.
Proof of Lemma 4.4. First we recall that the Fiedler value is the value obtained
by
min
a i;j
(2)
and a Fiedler vector is a vector that achieves this minimum. We note that if we
replace A by a matrix that is at least as large on an elementwise comparison then
x T LAx cannot decrease for any vector x.
We consider A(J ; J ), the diagonal block of A indexed by J . By the definition
of an R-matrix, all values in A(J ; J ) must be at least as large as a r;s . However, a r;s
must be greater than zero. Otherwise, by the R-matrix property a
then by the statement of the theorem
a which would make the matrix
reducible.
The remainder of the proof will proceed in two stages. First we will force all the
off-diagonal values in A(J ; J ) to be a r;s and show the result for this modified matrix.
We will then extend the result to our original matrix.
Stage 1:
We define the matrix B to be identical to A outside of B(J ; J ), but all off-diagonal
values of B within B(J ; J ) are set to ff = a r;s . It follows from the hypotheses that B
is an R-matrix. We define note that, by the R-matrix property,
We now define ~
ff)I and consider the eigenvalue equation ~
~
This matrix has the same eigenvectors as LB with eigenvalues shifted by
rows of ~
LB in J are identical. Consequently,
either all elements of x in J are equal, or ~ - (which is equivalent to -
We will show that irreducibility and a which will complete
the proof of Stage 1.
We assume look for a contradiction. We introduce a new matrix
B as follows
ff otherwise.
Since B is an R-matrix, -
B is at least as large as B elementwise, so - 2 ( -
We define the vector -
y by
and -
x to be the unit vector in the direction of -
y. We note that -
and that
We have the following chain of inequalities.
The last inequality is strict since - b
then we can combine an inequality due to Fiedler [10],
l ii ;
with the observation that min i l i;i - ffi to obtain - 2 - n
. This can
only be true if equality holds throughout, implying that
But this contradicts (3), so - 2 ff and the proof of Stage 1 is complete.
Stage 2:
We will now show that A and B have the same Fiedler vectors. Since A is elementwise
at least as large as B, for any vector z, z T LA z - z T LB z. From Stage 1 we know that
any Fiedler vector of B satisfies x . In this vector,
for so the contribution to the sum in (2) from B(J ; J ) is zero. But this
contribution will also be zero when applied to A(J ; J ). Since A and B are identical
outside of A(J ; J ) and B(J ; J ), we now have that a Fiedler vector of B gives an
upper bound for the Fiedler value of A; that is, It follows that the
Fiedler vectors of B are also Fiedler vectors of A and vice versa.
5. A spectral algorithm for the seriation problem. We can now bring all
the preceding results together to produce an algorithm for well-posed instances of the
seriation problem. Specifically, given a well-posed correlation function we will generate
all consistent orderings. Given a pre-R matrix, our algorithm constructs a PQ-tree
for the set of permutations that produce an R-matrix.
Our Spectral-Sort algorithm is presented in Fig. 1. It begins by translating all
the correlations so that the smallest is 0. It then separates the irreducible blocks (if
there are more than one) into the children of a P-node and recurses. If there is only
one such block, it sorts the elements into the children of a Q-node based on their
values in a Fielder vector. If there are ties in the entries of the Fiedler vector, the
algorithm is invoked recursively.
Input: A, an n \Theta n pre-R matrix
U , a set of indices for the rows/columns of A
Output: T , a PQ-tree that encodes the set of all permutations -
such that A - is an R-matrix
begin
(1) ff := min i6=j a i;j
(1) A := A \gamma ffee T
:= the irreducible blocks of A
:= the corresponding index sets
else
(3) else if
else
Fiedler vector for LA
number of distinct values in x
indices of elements in x with jth value
Fig. 1. Algorithm Spectral-Sort.
We now prove that the algorithm is correct. Step (1) is justified by Lemma 4.1,
and requires time proportional to the number of nonzeros in the matrix. The identification
of irreducible blocks in step (2) can be performed with a breadth-first or
depth-first search algorithm, also requiring time proportional to the number of nonze-
ros. Combining the permutations of the resulting blocks with a P-node is correct by
Lemma 4.2.
Step (3) handles the boundary conditions of the recursion, while in step (4) the
Fiedler vector is computed and sorted. If there are no repeated elements in the Fiedler
vector then the Q-node for the permutation is correct by Theorem 3.3. Steps (3) and
(4) are the dominant computational steps and we will discuss their run time below.
The recursion in step (5) is justified by Theorem 4.7.
Note that this algorithm produces a tree whether A is pre-R or not. To determine
whether A is pre-R, simply apply one of the generated permutations. If the result
is an R-matrix then all permutations in the PQ-tree will solve the seriation problem,
otherwise the problem is not well posed.
The most expensive steps in algorithm Spectral-Sort are the generation and
sorting of the eigenvector. Since the algorithm can invoke itself recursively, these
operations can occur on problems of size n, n if the time for an eigen-
calculation on a matrix of size n is T (n), the runtime of algorithm Spectral-Sort is
A formal analysis of the complexity of the eigenvector calculation can be simplified
by noting that for a Pre-R matrix, all that matters is the dominance relationships between
matrix entries. So, without loss of generality, we can assume that all entries are
integers less than n 2 . With this observation, it is possible to compute the components
of the Fiedler vector to a sufficient precision that the components can be correctly
sorted in polynomial time. We now sketch one way this can be done, although we
don't recommend this procedure in a real-world implementation.
Let - denote a specific eigenvalue of L, in our case the Fiedler value. This can
be computed in polynomial time as discussed in [25]. Then we can compute the
corresponding eigenvector x symbolically by solving
where p(z) is the characteristic polynomial of L. Gaussian elimination over a field is in
P [21], so if p(z) is irreducible we obtain a solution x where each component x i is given
by a polynomial in z with bounded integer coefficients. We note that letting z be any
eigenvalue will force x to be a true eigenvector. If p(z) is reducible, we try the above.
If we fail to solve the equation, we will instead find a factorization of p(z) and proceed
by replacing p(z) with the factor containing - as a root. This yields a polynomial
formula for each x i and we can identify equal elements by e.g. the method in [22]. To
decide the order of the remaining components, we evaluate the root - to a sufficient
precision and then compute the x i 's numerically and sort. Since - is algebraic, the
cannot be arbitrarily close [22] and polynomial precision is sufficient.
In practice, eigencalculations are a mainstay of the numerical analysis community.
To calculate eigenvectors corresponding to the few highest or lowest eigenvalues (like
the Fiedler vector), the method of choice is known as the Lanczos algorithm. This is
an iterative algorithm in which the dominant cost in each iteration is a matrix-vector
multiplication which requires O(m) time. The algorithm generally converges in many
fewer than n iterations, often only O(
n) [26]. However, a careful analysis reveals a
dependence on the difference between the distinct eigenvalues.
6. The consecutive ones problem. Ordering an R-matrix is closely related
to the consecutive ones problem. As mentioned in x1, a (0; 1)-matrix C has the
consecutive ones property if there exists a permutation matrix \Pi such that for each
column in \PiC, all the ones form a consecutive sequence. 3 A matrix that has this
property without any rearrangement (i.e. I) is in Petrie form 4 and is called a P-
matrix. Analogous to R-matrices, we say a matrix with the consecutive ones property
is pre-P. The consecutive ones problem can be restated as: Given a pre-P matrix C,
find a permutation matrix \Pi such that \PiC is a P-matrix.
3 Some authors define this property in terms of rows instead of columns.
4 Sir William M. F. Petrie was an archaeologist who studied mathematical methods for seriation
in the 1890's.
There is a close relationship between P-matrices and R-matrices. The following
results are due to D.G. Kendall and are proved in [19] and [33].
Lemma 6.1. If C is a P-matrix, then is an R-matrix.
Lemma 6.2. If C is pre-P and is an R-matrix, then C is a P-matrix.
Theorem 6.3. Let C be a pre-P matrix, let A = CC T , and let \Pi be a permutation
matrix. Then \PiC is a P-matrix if and only if \PiA\Pi T is an R-matrix.
This theorem allows us to use algorithm Spectral-Sort to solve the consecutive
ones problem. First construct apply our algorithm to A (note that
the elements of A are small non-negative integers). Now apply one of the permutations
generated by the algorithm to C. If the result is a P-matrix then all the permutations
produce C1P orderings. If not, then C has no C1P orderings.
The run time for this technique is not competitive with the linear time algorithm
for this problem due to Booth and Lueker [5]. However, unlike their approach, our
Spectral-Sort algorithm does not break down in the presence of errors and can
instead serve as a heuristic.
Several other combinatorial problems have been shown to be equivalent to the
consecutive ones problem. Among these are recognizing interval graphs [5, 12] and
finding dense envelope orderings of matrices [5].
One generalization of P-matrices is to matrices with unimodal columns (a uni-modal
sequence is a sequence that is non-decreasing until it reaches its maximum,
then non-increasing). These matrices are called unimodal matrices [32]. Kendall [20]
showed that the results 6.1 - 6.3 are also valid for unimodal matrices if the regular
matrix product is replaced by the matrix circle product defined by
Note that P-matrices are just a special case of unimodal matrices, and that the circle
product is equivalent to matrix product for (0; 1)-matrices. Kendall's result implies
that our spectral algorithm will correctly identify and order unimodal matrices.

Acknowledgements

. We are indebted to Robert Leland for innumerable discussions
about spectral techniques and to Sorin Istrail for his insights into the consecutive
ones problem and his constructive feedback on an earlier version of this paper. We
are further indebted to David Greenberg for his experimental testing of our approach
on simulated genomic data, and to Nabil Kahale for showing us how to simplify the
proof of Theorem 3.2. We also appreciate the highly constructive feedback provided
by an anonymous referee.



--R

Interior point methods in semidefinite programming with applications to combinatorial optimization.
A spectral technique for coloring random 3-colorable graphs
Graph coloring using eigenvalue decomposition.
A spectral algorithm for envelope reduction of sparse matrices.
Testing for the consecutive ones property
A near optimal algorithm for edge seperators (preliminary version).
Recent Results in the Theory of Graph Spectra.
Spectra of Graphs: Theory and Application.
Lower bounds for the partitioning of graphs.
Algebraic connectivity of graphs.
A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory.
Incidence matrices and interval graphs.
An analysis of spectral envelope-reduction via quadratic assignment problems

Physical mapping by STS hybridization: Algorithmic strategies and the challenge of software evaluation.
Geometric Algorithms and Combinatorial Optimiza- tion
Optimal linear labelings and eigenvalues of graphs.
Approximate graph coloring by semidefinite program- ming
Incidence matrices
Abundance matrices and seriation in archaeology.
The Design and Analysis of Algorithms.
of algebraic numbers.
The Laplacian spectrum of graphs.
Laplace eigenvalues of graphs - a survey
Algebraic complexity of computing polynomial zeros.
The Lanczos algorithm with selective orthogonalization.
Zur Theorie der Matrizen.
Partitioning sparse matrices with eigenvectors of graphs.
A method for chronologically ordering archaeological deposits.
Matrix Iterative Analysis.
Approximation of the consecutive ones matrix augmentation problem.
Mathematics in the Archaeological and Historical Sciences
Techniques of data analysis and seriation theory.
--TR

--CTR
Antonio Robles-Kelly , Edwin R. Hancock, Graph Edit Distance from Spectral Seriation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.365-378, March 2005
Jordi Petit, Experiments on the minimum linear arrangement problem, Journal of Experimental Algorithmics (JEA), 8,
Aristides Gionis , Teija Kujala , Heikki Mannila, Fragments of order, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Anil Menon, Aspects of the Binary CMAC: Unimodularity and Probabilistic Reconstruction, Neural Processing Letters, v.22 n.3, p.263-276, December  2005
Antti Ukkonen , Mikael Fortelius , Heikki Mannila, Finding partial orders from unordered 0-1 data, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Huaijun Qiu , Edwin R. Hancock, Graph matching and clustering using spectral partitions, Pattern Recognition, v.39 n.1, p.22-34, January, 2006
Sebastian Lange , Martin Middendorf, Design Aspects of Multi-level Reconfigurable Architectures, Journal of Signal Processing Systems, v.51 n.1, p.23-37, April     2008
consecutive ones property;eigenvector;analysis of algorithms;fiedler vector;seriation