{'fraction_non_alphanumeric': 0.0408420852087352, 'fraction_numerical': 0.014931771093805815, 'mean_word_length': 4.032598274209012, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The seriation problem in the presence of a double Fiedler value

Seriation is a problem consisting of seeking the best enumeration order of a set of units whose interrelationship is described by a bipartite graph, that is, a graph whose nodes are partitioned in two sets and arcs only connect nodes in different groups. An algorithm for spectral seriation based on the use of the Fiedler vector of the Laplacian matrix associated to the problem was developed by Atkins et al., under the assumption that the Fiedler value is simple. In this paper, we analyze the case in which the Fiedler value of the Laplacian is not simple, discuss its effect on the set of the admissible solutions, and study possible approaches to actually perform the computation. Examples and numerical experiments illustrate the effectiveness of the proposed methods.

1. Introduction. By seriation, we refer to an important ordering problem that aims at recovering the best enumeration order of a set of units in terms of a chosen correlation function. Such order can be chronological, or any sequential structure which characterizes the data. The notion of seriation has been formulated in several ways and appears in various fields, such as archaeology, anthropology, psychology, and biology [4,9,14,18]. The first systematic formalization of the seriation problem was made by Petrie in 1899 [20], even if the term seriation was used before in archaeology; see Concas et al. [6] for an overview.
When the ordering is chronological, seriation concerns relative dating of objects or events, which is employed when absolute dating methods cannot be used. This means that the order lacks a direction, in the sense that the units are placed in a sequence which can be read in both directions. Seriation finds another application in de novo genome sequencing. In this case, from a randomly oversampled DNA strand (the so-called reads) the whole sequence is reconstructed. Oversampling is necessary to increase the probability of all parts being covered. The reads which overlap are then considered as similar and their ordering is obtained by placing similar reads close to each other.
In all the applications, seriation data are usually given in terms of a matrix of size n × m, called the data matrix, whose row and/or column indices represent the elements to be ordered. In archaeology, the rows of the data matrix correspond to the units (e.g., the sites) and the columns represent the types of the archaeological findings detected in the units. Each unit is characterized by the presence of certain artefacts, which are in turn classified in types. Piana Agostinetti and Sommacal [21], the authors refer to the data matrix as either incidence matrix or abundance matrix, depending on the archaeological data representation. In the first case, the data are reported by using a binary representation, i.e., an element in the position (i, j) is equal to 1 if type j is present in the unit i, and 0 otherwise. In the second case, each element of the data matrix reports the number of objects belonging to a certain type in a given unit, or its percentage. In this paper, following the usual terminology used in complex networks theory, we will refer to the binary representation as an adjacency matrix. More details can be found in [6]. The purpose of determining a relative chronology consists of obtaining an ordering of the rows and columns of the data matrix that places the nonzero entries close to its diagonal. Given the variety of applications, some software packages have been developed in the past to manipulate seriation data; see [6] for an overview.
A spectral algorithm for the solution of the seriation problem was considered by Atkins et al. [1], and an optimized Matlab implementation has recently been proposed by Concas et al. [6]. Each solution is a permutation of the nodes which solves a particular optimization problem. The method is based on the use of the Fiedler vector of the Laplacian matrix associated with the problem, and describes the set of solutions in terms of a data structure known as a PQ-tree. In this paper, we discuss the implications of the presence of a multiple Fiedler value, an issue which has been disregarded up to now. Our interest is mainly for the case of multiplicity two, for which we illustrate the effects on the set of solutions.
The plan of the paper is the following. Section 2 reviews the necessary mathematical background, sets up the terminology to be used in the rest of the paper, and describes the data structures used to store the solutions of the seriation problem. The spectral algorithm and the special case of a multiple Fiedler value are discussed in Section 3. In Section 4, we extensively analyze three example networks whose Laplacian admits a double Fiedler value, showing the consequences on the set of solutions of the seriation problem. Section 5 describes two practical algorithms for computing the admissible solutions, and Section 6 reports some numerical results. Finally, Section 7 contains concluding remarks.

Mathematical background.
Here we review some mathematical concepts that will be used in the following. Matrices will be denoted by upper case roman letters, vectors by lower case bold letters, and their elements by lower case doubly and singly indexed letters, respectively.
Let G be a simple graph with n nodes. The adjacency matrix F ∈ R n×n associated to G contains in position (i, j) the weight of the edge connecting node i to node j. If the two nodes are not connected, then f ij = 0. If a graph is unweighted, then the weights are either 0 or 1. The adjacency matrix is symmetric if the graph is undirected.
The (unnormalized) graph Laplacian of a symmetric irreducible matrix F ∈ R n×n is the symmetric, positive semidefinite matrix is the degree matrix, whose ith diagonal element equals the sum of the weights of all the edges starting from node i in the undirected network defined by F , that is, d i = n j=1 f ij . In the case of an unweighted graph, d i is simply the number of nodes connected to node i. It is immediate to observe that 0 is an eigenvalue of the graph Laplacian, with associated eigenvector e = (1, . . . , 1) T ∈ R n , and that all the eigenvalues λ 1 = 0 ≤ λ 2 ≤ · · · ≤ λ n are non-negative.
The smallest eigenvalue of L with associated eigenvector orthogonal to e is called the Fiedler value, or the algebraic connectivity, of the graph described by F . The corresponding normalized eigenvector is the Fiedler vector [11,12,13]. Alternatively, the Fiedler value may be defined to be any vector x that achieves the minimum In this paper we describe the seriation problem in terms of bipartite graphs, since the interrelationship between the units to be reordered can be expressed in terms of such graphs. A bipartite graph G is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a node in U to one in V . In our archaeological metaphor the sets U and V , containing n and m nodes respectively, represent the units and the types of the findings. Hence, the adjacency data matrix A ∈ R n×m associated to the seriation problem can be interpreted as the matrix which describes the connections in the bipartite graph associated to the problem and it is obtained by setting a i,j = 1 if unit i contains objects of type j and 0 otherwise.
One approach for solving the seriation problem is based on the construction of a symmetric similarity matrix S, whose elements s ij describe the likeness of the nodes i, j ∈ U [3,23]. One possible definition for it is through the product S = AA T , being A the adjacency matrix of the bipartite graph associated to the problem. In this case, s ij equals the number of types shared between unit i and unit j. The largest value on each row is the diagonal element, which reports the number of types associated to each unit. By applying the same permutation to the rows and columns of S in order to cluster the largest values close to the main diagonal, one obtains the permutation of the rows of A that brings close the units more similar for what concerns types. It is worth noting that this rows and columns permutation is not uniquely defined.
The Robinson method [23] is a technique based on a different similarity matrix. Starting from an abundance matrix A ∈ R n×m whose entries are in percentage form (the sum of each row is 100), it computes the similarity matrix S by a particular rule, leading to a symmetric matrix of order n with entries between 0 (rows with no types in common) and 200, which corresponds to units containing exactly the same types. Then, the method searches for a permutation matrix P such that P SP T has its largest entries as close as possible to the main diagonal. The same permutation determines the chronological order for the units.
The procedure of finding a permutation matrix P is not uniquely specified. One way to deal with it is given by the so called Robinson's form, which places larger values close to the main diagonal, and lets off-diagonal entries be nonincreasingly ordered moving away from the main diagonal. Such a matrix is also called R-matrix, or it is said to be in R-form; see [6] for details. A symmetric matrix is pre-R if and only if there exists a simultaneous permutation of its rows and columns which takes it to Robinson's form, so it corresponds to a well-posed ordering problem; see [5,16,17,22,24].
A subset of the possible permutations of the elements of a set can be encoded in a data structure called PQ-tree, originally introduced by Booth and Lueker [2]. A PQ-tree T over a set U = {u 1 , u 2 , . . . , u n } is a rooted tree whose leaves are elements of U and whose internal (non-leaf) nodes are distinguished as either P-nodes or Q-nodes. The only difference between them is the way in which their children are treated. In particular, the children of a P-node can be arbitrarily permuted, while the order of those of a Q-node can only be reversed. The root of the tree can either be a P or a Q-node; see [6] for a Matlab implementation of PQ-trees.
We now briefly review the spectral algorithm for the seriation problem introduced in [1] and implemented in [6]. Starting from a pre-R matrix, it constructs a PQ-tree describing the set of all the row and column permutations that lead to an R-matrix.
Given the set of units U = {u 1 , u 2 , . . . , u n }, the notation i j indicates that u i precedes u j in a chosen ordering. Then, a symmetric bivariate correlation function f can be used to describe the desire for units i and j to be close to each other in the sought sequence; see [1]. The aim of the algorithm is to find all index permutation vectors π = (π 1 , . . . , π n ) T such that π i π j π k ⇐⇒ f (π i , π j ) ≥ f (π i , π k ) and f (π j , π k ) ≥ f (π i , π k ). (2.1) Setting f ij = f (i, j) defines a matrix F with the same role as the similarity matrix S aforementioned. If a seriation data set is described by an adjacency (or abundance) matrix A, we set F = AA T . If F is pre-R, there exists a row/column permutation that takes it in R-form. Unfortunately, this property cannot be stated in advance in general.
The approach adopted in [1] (see also [10]) is to consider the constrained optimization problem The value of the function h(x) is small for a vector x such that each pair (u i , u j ) of highly correlated units is associated to components x i and x j with close values. Once the minimizing vector x min is computed, it is sorted according to either nonincreasing or nondecreasing values, yielding x π = (x π1 , . . . , x πn ) T . The permutation π of the units realizes (2.1). Letting D = diag(d i ) be the degree matrix, the previous minimization problem can be rewritten as where L = D − F is the Laplacian of the correlation matrix F . The two constraints require that x be a unit vector orthogonal to e. This shows, by the Courant-Fischer-Weyl min-max principle, that any Fiedler vector is a solution to the constrained minimization problem.
The problem is well posed only when F is pre-R. Nevertheless, a real data set may be inconsistent, in the sense that it may not necessarily lead to a pre-R similarity matrix. In such cases, it may be useful to construct an approximate solution to the seriation problem, and sorting the entries of the Fiedler vector generates an ordering that tries to bring highly correlated elements close to each other. We refer to such orderings as admissible permutations.

Multiple Fiedler values in seriation.
In this section we analyze the case of the presence of a multiple Fiedler value and its effect on the spectral algorithm discussed above.
Let us assume that the Fiedler value has multiplicity k, and let q 1 , . . . , q k be an orthonormal basis of the corresponding eigenspace F . For each x ∈ F , there is a vectorỹ = (y 1 , . . . , y k ) T such that where Q k = [q 1 , . . . , q k ]. We remind the reader that a solution to the seriation problem is determined by sorting the vector x either nonincreasingly or nondecreasingly. When k = 1 there is in general only one permutation which solves the problem, together with its reverse. There are multiple solutions if the eigenvector x has ℓ multiple equal components. In this case, there will be ℓ! solutions.
When k > 1, after extending Q k to a square orthogonal matrix Q, we can write x = Qy, with Although it is clear that only the first k entries are relevant in determining x, it is not trivial to understand how many permutations are allowed to sort x when the components ofỹ vary. Let us analyze the situation where q i = e i , the vectors of the canonical basis in R n , i = 1, . . . , k, so that we may set Q = I, Even in the case x = y, the conclusion is not trivial. If the first k components of y are different from zero and distinct, then the indexes associated to the last n − k zero components admit (n − k)! equivalent permutations. We can consider such indexes in the whole vector y as grouped in a unique "vector" index, as the corresponding components all share the same position in each possible sorting. Under this assumption, the number of different orderings for y is (k + 1)!. Substituting to the vector index all its possible permutations, the number of admissible solutions grows to If there are groups of equal components inỹ, this number is going to increase accordingly. The truth is that in the general case, that is when Q = I, the number of admissible permutations depends upon the structure of the Fiedler vectors. Concas et al. [6] pointed out that non pre-R matrices can lead to Laplacian matrices whose Fiedler value is not simple and conjectured, through the following simple example, that the number of permutations (3.2) may be incorrect.
Let us consider the seriation problem described by the bipartite graph depicted in Figure 4.3 (left). The relationship between nodes on the left (units) and nodes on the right (types) is represented by edges. The adjacency matrix of this graph and the resulting similarity matrix are, respectively Note that S can be seen as the adjacency matrix of the graph shown in Figure 4.3 (right). A solution to the seriation problem does not exist in this case, since the associated graph describes a cycle: each unit is similar to surrounding units and the two extremal units are similar to each other. This leads to a non pre-R similarity matrix. As shown in [6], the Fiedler value of the Laplacian L = D − F has multiplicity 2, so each vector belonging to the Fiedler plane can be sorted to obtain the admissible permutations of the units. In the same paper, the authors considered a randomized approximated approach, which will be discussed in Section 5, to determine such permutations. They found only 5 admissible permutations, much less than the number (k + 1)!(n − k)! = (2 + 1)!(5 − 2)! = 36 determined in (3.2).
In this paper, we will show that this estimate for the number of admissible permutations was wrong, nevertheless, we will confirm the fact that when a Fiedler value is multiple some constraints are imposed on the admissible permutations of the units. In particular, we will show that their number does not only depend on the multiplicity of the Fielder value, but also on the structure of the underlying bipartite graph.
In the following, we often focus on the number of permutations found. Referring to such a number is significant only to show that, in the cases analyzed, the number of admissible solutions is always smaller than the forecast given by (3.2). We stress the fact that solving the seriation problem consists of listing all the admissible permutations of the nodes. Any theoretical analysis or numerical algorithm must be able to produce such result.
4. Three case studies. In this section, to gain insight in the behavior of other similar examples, we analyze three different graphs whose Laplacian exhibits a double Fiedler value: the modified star graph, the cycle graph, and the generalized Petersen graph.
4.1. The modified star graph. Consider the bipartite graph represented in Figure 4.1 (left) whose associated data matrix is where e k = (1, . . . , 1) T ∈ R k , and I k denotes the identity matrix of size k. As already stated, e i,j = 1 indicates that unit i contains objects of type j. The resulting similarity and Laplacian matrices are given by s ij , is the degree matrix associated to S. The matrix S can be interpreted as the adjacency matrix of a star graph; see Figure 4.1 (right). A star graph S n is a connected graph with n vertices and n − 1 edges, where one vertex, the center of the star, has degree n − 1 and the other n − 1 vertices have degree 1. It is a special case of a complete bipartite graph in which one set has one vertex and the other set contains the remaining n − 1 vertices.
Both the Laplacian and the similarity matrix (4.2) are arrowhead matrices, that is, real symmetric matrices of the form where α is a scalar, z ∈ R n−1 , and ∆ = diag(δ 1 , . . . , δ n−1 ). From the Cauchy interlacing theorem [26] for the eigenvalues of Hermitian matrices, it follows that the sorted eigenvalues λ 1 , . . . , λ n of (4.3) interlace the sorted elements δ i of the diagonal matrix ∆. If δ 1 ≥ δ 2 ≥ · · · ≥ δ n−1 and if the eigenvalues λ i , i = 1, . . . , n, are sorted accordingly, then the following inequality holds If δ i = δ i−1 for some i, the above inequality implies that δ i is an eigenvalue of the arrowhead matrix (4.3) considered.
The following theorem identifies the eigenvalues of the Laplacian matrix in the case of a star graph.
Theorem 4.1. Let S be the adjacency matrix of a star graph S n . Then, the spectrum of the Laplacian matrix L consists of the three eigenvalues 0, 1, and n, with the second having multiplicity n − 2.
Proof. A well known result states that the smallest eigenvalue of the Laplacian is λ n = 0. From the Cauchy interlacing theorem applied to the matrix L in (4.2), it follows (see (4.4)) that 1 is an eigenvalue with multiplicity n − 2. Setting v = (−(n − 1), 1, . . . , 1) T ∈ R n , we see that Lv = nv, so that λ 1 = n. Proof. Without loss of generality we can assume that the first node is the central one of degree n−1. To determine the Fiedler vectors one has to solve the homogeneous linear system (L − I n )v = 0, whose coefficient matrix is of the form The last n − 1 equations of the system show that the first component of the Fiedler vectors is always 0, while the first equation implies that the sum of their components is 0.
Since we are focusing on the case of a double Fiedler value, let us consider the modified star graph. In the bipartite graph of Figure 4.1, we add n − 4 nodes to the set of the types, and connect each of these nodes to two consecutive nodes in the set of units, except the first ones. We obtain the bipartite graph in Figure 4.2 (left). The seriation data matrix associated to this graph is where 0 k ∈ R k is a null vector, and B k,ℓ ∈ R k×(k−ℓ) is the lower bidiagonal matrix whose elements are 1 on the main diagonal and on the sub-diagonal, and zero otherwise.
The resulting similarity matrix is where O denotes a null matrix of suitable size and T n−3 is the tridiagonal matrix  The similarity matrix S can be seen as the adjacency matrix of the modified star graph in Figure 4.2 (right), which we denote by S 6 . The Laplacian matrix of S is given by where O denotes a null matrix of suitable size and T n−3 is like (4.6), but with the elements in the sub-and in the super-diagonal of opposite sign.
The following theorem explains the behavior of the Fiedler value of the Laplacian matrix in the case of the modified star graph S n . Theorem 4.3. Let S be the adjacency matrix of a modified star graph S n . Then, the spectrum of the Laplacian matrix L (4.7) contains the three eigenvalues 0, 1, and n, with the second having multiplicity 2, while the remaining n − 4 eigenvalues are in the interval (1,5).
Proof. A direct computation shows that λ 1 = 0, λ 2 = λ 3 = 1, and λ n = n, are eigenvalues of L with associated eigenvectors By a simple application of the Gram-Schmidt process, we see that any vector orthogonal to v 1 , v 2 , and v n has a null first and last component, like v 3 . So, the remaining n − 4 eigenvectors take the form withṽ ∈ R n−2 . Given the expression (4.7) of matrix L, any such vectorṽ is an eigenvector of the principal submatrix Besides the eigenvalue λ 2 = 1, the remaining eigenvalues of L are those of T n−3 . The Gershgorin circle theorems applied to T n−3 yields 1 ≤ λ i < 5, i = 3, . . . , n−1. It is immediate to observe that λ 3 = 1 with associated eigenvector e n−3 . It is a simple eigenvalue because a symmetric tridiagonal matrix with nonzero subdiagonal elements has distinct eigenvalues [19]. This completes the proof.
Corollary 4.4. Let S be the adjacency matrix of a modified star graph S n . Then, its Fiedler value is equal to 1 and has multiplicity 2.
In the case of the modified star graph S n , an orthogonal basis for the eigenspace F corresponding to the Fiedler value is given by where q 1 = v 3 and q 2 = v 2 . For the sake of simplicity, we do not normalize the two eigenvectors. Letting y = (α, β) T ∈ R 2 \ {(0, 0)}, every x ∈ F can be expressed as The admissible permutations are then related to the possible reorderings of the entries of x ∈ F , and these sortings depend on the values of the coefficients α and β. We remark that they cannot be both zero, as x is an eigenvector.
We let x 1 = 0, x 2 = −α − β, x n−1 = (n − 3)α − β, and x n = (n − 2)β. The relative position of such components is governed by the following inequalities, where we initially consider only strict inequality for α < n−1 n−3 β. When considering a particular ordering of the vector x, multiple index permutations are produced by permuting the components of the vector x 2 = (x 2 , . . . , x 2 ) T ∈ R n−3 , containing the equal components in (4.8). To identify such permutations we consider the following cases: 1. α, β > 0: in correspondence to the three inequalities we find the following increasingly ordered vectors x,     2. α > 0 > β: now, the three inequalities correspond to the sorted vectors   The above cases are exhaustive. Indeed, the inequalities α, β < 0 and α < 0 < β produce permutations which are the reverse of the ones already considered in 1 and 2, respectively. The total number of permutations accounted for so far is We now consider equalities in (4.9), that is, we seek the values of the parameters α and β for which some components of the vector x in (4.8) become equal, besides those of x 2 .
It is important to remark that if two scalar components are equal, no new permutations are introduced. For example, (n − 3)α = β makes x 1 = x n−1 , but the vector orderings deriving from the permutation of these two components have already been considered in the first two vectors of (4.11).
On the contrary, when x 2 is equal to any of the three other different components, then new index permutations are generated by permuting the considered component with the entries of the vector x 2 . When α ≥ 0 > β, the special cases where x 2 = x 1 , x 2 = x n−1 , and x 2 = x n , correspond to the conditions α = −β, α = 0, α = −(n − 1)β, respectively, and lead to the sorted vectors  where Each vector in (4.14) produces (n − 2)! index permutations, from which one must subtract those already considered in (4.11) and (4.13). For example, for the first vector of (4.14) the permutations have already been accounted for in the first two vectors of (4.13). This leads to 4.2. The cycle graph. The second example of a graph whose Laplacian has a multiple Fiedler value is the cycle or circular graph C n , whose vertices are connected in a closed chain. The number of edges in C n equals the number of vertices and, since every node has exactly two edges incident to it, every vertex has degree 2. Hence a cycle is a regular graph, i.e., a graph in which each vertex has the same degree k.
Consider the bipartite graph represented in Figure 4.3 (left) with associated data matrix where B n,1 ∈ R n×(n−1) is the lower bidiagonal matrix defined in (4.5) and b n = (1, 0 T n−2 , 1) T , being 0 k the null vector of length k. As B T n,1 b n = b T n−1 , its similarity matrix and Laplacian are, respectively, and C n−1 is the tridiagonal matrix like C n−1 , with the elements in the sub-and super-diagonal of opposite sign. The matrix S can be seen as the adjacency matrix of a cycle graph C n ; see Figure 4.3. The matrix L is circulant, that is, it is fully specified by its first column, while the other columns are cyclic permutations of the first one with an offset equal to the column index [8]. A basic property of a circulant matrix C is that its spectrum is analytically known. It is given by is the discrete Fourier transform of the first column (c 0 , c 1 , . . . , c n−1 ) T of C, ω = e 2πi n is the minimal phase nth root of unity, and i the imaginary unit. The next theorem states the behavior of the eigenvalues of the Laplacian matrix in the special case of a circular graph. where ⌊m⌋ denotes the minimal integer part of m. In particular, if n is odd λ 1 = 0 is the only simple eigenvalue. If n is even, the eigenvalues λ 1 = 0 and λ n/2 , of smallest and largest modulus, respectively, are the only simple ones. The property trivially results from L being a symmetric circulant matrix. For the sake of clarity, we give a simple proof.
Proof. First, we recover a well known result in graph theory which states that the eigenvalue of smallest modulus of the Laplacian is λ 1 = 0. Indeed, from (4.18) and (4.19), it follows that the discrete Fourier transform of the first column of L is and that λ 1 = L(1) = 0. Next, let k = 1, . . . , n − 1. From (4.18) and (4.19) we obtain where θ k = − 2πi n k. The thesis follows from the property ω k = ω n−k . The theorem immediately implies the following. The normalized eigenvectors of an n × n circulant matrix are the columns of the normalized Fourier matrix, that is, , ω 2(j−1) , . . . , ω (n−1)(j−1) T , j = 1, . . . , n. (4.20) A basis for the eigenspace corresponding to the Fiedler value is given by {v 2 , v n }, where the entries of v n are the conjugates of those of v 2 . To obtain eigenvectors with real entries we consider the vectors with components (w 1 ) j = cos 2(j − 1)π n , (w 2 ) j = sin 2(j − 1)π n , j = 1, . . . , n.
These vectors are, in fact, connected to the discrete cosine transform (DCT) and the discrete sine transform (DST), respectively. They have many symmetries, and more relations are valid for n either odd or even. Every Fiedler vector x lies in the eigenspace generated by w 1 and w 2 , so that it can be expressed as for α and β ∈ R. Anyway, because of the many symmetries in the vectors w 1 and w 2 , it is impracticable to find a general rule to find the number of admissible permutations, i.e., of all the possible reorderings of the components of x for any n. The task is made harder by the fact that for specific values of the coefficients α and β, groups of components of the Fiedler vector x take the same value, generating bunches of admissible permutations. We analyzed in detail the situation for n = 4, 5, 6, 7, determining 8, 15, 30, and 49 permutations, respectively. These results will be confirmed numerically in Section 6. We report here the permutations obtained for n = 4 We remark, that according to formula (3.2) the number of admissible solutions for n = 4, 5, 6, 7 should be 12, 36, 144, and 720, respectively.

4.3.
The generalized Petersen graph. The generalized Petersen graph is another graph whose Fiedler value has multiplicity 2. It was introduced by Coxeter [7] and it was given its name later, in 1969, by Watkins [25]. We denote it by GP G(n, k). It has 2n vertices and 3n edges given, respectively, by where the subscripts are expressed as integers modulo n (n ≥ 5) and k is the so called "skip". Let U(n, k) (respectively, V(n, k)) be the subgraph of GP G(n, k) consisting of the vertices {u i |1 ≤ i ≤ n} (respectively, {v i , 1 ≤ i ≤ n}) and edges {u i u i+1 |1 ≤ i ≤ n} (respectively, {v i v i+k |1 ≤ i ≤ n}). We will call U(n, k) (respectively, V(n, k)) the outer (respectively, inner) subgraph of GP G(n, k).
The 2n×2n data matrix of the bipartite graph GP G(n, k) has the block structure where I n is the n × n identity matrix, the block U is the adjacency matrix of the outer subgraph U(n, k), it coincides with the adjacency matrix S (4.17) of a cycle graph, with the diagonal elements equal to 3. The block V k is the adjacency matrix for the inner graph V(n, k), whose structure is determined by the skip k. The matrices U and V k are circulant. They are specified by their first column given, respectively, by where 0 j denotes the null vector of length j, or the empty vector when j = 0. We will write U = circ(c) and V k = circ(c (k) ). We consider the data matrix represented by the graph in Figure 4.4 (left) for n = 5 whose similarity matrix can be seen as the adjacency matrix of the generalized Petersen graph GP G(n, k) with a skip k = 1; see Figure 4.4 (right). In this particular case, also the inner subgraph is a cycle graph and the incidence matrix has the block structure where E ∈ R n×n is the incidence matrix of the cycle defined in (4.16). Its similarity matrix and Laplacian are, respectively where F and F are n × n circulant matrices given respectively by Theorem 4.7. Let E be the 2n×3n data matrix (4.24) of the generalized Petersen graph GP G(n, 1). Then, the Fiedler value of the Laplacian matrix L has multiplicity 2.
Proof. L is a block circulant matrix with circulant blocks F and −I n . A block circulant matrix can be expressed as the sum of Kronecker products. In our case, we have where P 1 = I 2 and P 2 = circ(0, 1). More in general, one has P i = circ(e i ), with e i the ith canonical basis vector. If we define the matrix-valued function so that H(P 2 ) = L, it can be shown (see [15]) that the spectrum of L is the union of the spectra of H(λ 1 ) and H(λ 2 ), being λ 1 and λ 2 the eigenvalues of P 2 . Moreover, the eigenvectors of L are given by the Kronecker products v i ⊗ u j , i, j = 1, 2, where v i are the eigenvectors of P 2 and u i are the eigenvectors of both H(λ 1 ) and H(λ 2 ).
An immediate result is that the eigenvalues of L are given by where σ i , i = 1, . . . , n, are the eigenvalues of the matrix F . Since F is symmetric circulant, its eigenvalues are coupled (see Theorem 4.5) and this completes the proof.
Corollary 4.8. Let σ be the second smallest eigenvalue of the matrix F (4.26) and {w 1 , w 2 } be a basis for the eigenspace corresponding to σ. Then, σ − 1 is the Fiedler value of the Laplacian matrix L given in (4.25) and {v 1 , v 2 } is a basis for the associated eigenspace, where Proof. The proof follows from Theorem 4.7, noting that (1, 1) T is the eigenvector of P 2 associated to the eigenvalue λ 1 = 1.
Since the eigenvectors of the matrix F are the columns of the normalized Fourier matrix, we can obtain the set of admissible permutations from the results obtained for the cycle graph. Indeed, the vectors v 1 and v 2 defined in (4.27) have the same entries as the vectors w 1 and w 2 in (4.21), but each entry is doubled. This means that the components of a vector x in the Fiedler plane come in pairs. Consequently, the number of the admissible permutations for a generalized Petersen graph GP G(n, 1) is 2 n times the admissible permutations obtained for a cycle graph.

5.
Two numerical methods to determine admissible permutations. A possible approach to find the admissible permutations associated to a Fiedler vector in the presence of a multiple Fiedler value is to employ a randomized algorithm.
To this end, we developed a simple Monte Carlo approach. In the case of a double Fiedler value, we considered N random vectors in R 2 and used their components as coefficients of linear combinations of an orthonormal basis for the corresponding eigenspace; see (3.1). This procedure generates a set of random vectors belonging to a plane immersed in R n , which can all be considered as legitimate "Fiedler vectors". Each vector is then sorted and the corresponding permutations of indexes are stored in the columns of a matrix. After removing all the repeated permutations and the swapped ones, we obtain a set of allowed permutations of the n nodes in the considered graph.
The advantages of this approach are an easy implementation and its immediate generalization to the case of a Fiedler value with multiplicity larger than 2. The drawbacks are a large computational cost and the fact that this method is not able to identify permutations deriving from specific values of the coefficients of the linear combination; see for example the permutations produced by the Fiedler vectors (4.14) for the modified star graph. This aspects will be investigated in the numerical examples of Section 6, where we will apply this numerical method and the following one to the case studies considered in Section 4. In order to compute all the admissible permutations in the particular case of a Fielder value with multiplicity 2, we developed a graphical method which is briefly described below.
Let the Laplacian matrix L of a graph with n nodes have a double Fiedler value λ 2 , and let To illustrate the functioning of the graphical method, we consider the cycle graph with n = 5 nodes, depicted in  (4.22), there are intersection points with the same abscissa highlighted by vertical dashed lines. As explained above, the first admissible permutation is obtained by considering the position of the lines before the first intersection points and therefore it is given by (5 4 1 3 2). The first vertical dashed line points out that there are two pair of lines that intersect and consequently, the second set of allowed permutations is obtained from the first one by considering the two macro-nodes (1,4) and (2,3), that is, swapping the indexes corresponding to the lines that represent nodes 1 and 4 and nodes 2 and 3. Hence, the additional permutations are given by After the first intersection, the position of the lines gives the permutation of the nodes (5 1 4 2 3), which has already been considered. The second vertical dashed line, corresponding to the second intersection point, reveals that two pair of lines intersect, i.e., we need to consider two macro-nodes, namely (1,5) and (2,4). The new admissible permutations are then After the second intersection, the lines follow the order (1 5 2 4 3), that is contained in the previous set. In correspondence to the third intersection we have two pairs of lines which intersect, i.e., the Fielder vectors have the two macro-nodes (2,5) and (3,4). In this case, the encoded permutations are 6. Numerical experiments. In this section we report the results produced by the two methods introduced in Section 5 for determining the admissible permutations of a set of units, in the case the Fiedler value of the associated graph has multiplicity 2. To verify the performance of the methods, the graphical (see Algorithm 1) and the Monte Carlo methods have been implemented in Matlab R2021a and applied to the three case studies described in Section 4. The numerical experiments were performed on an Intel Xeon Gold 6136 computer (16 cores, 32 threads) equipped with 128 GB RAM, running the Linux operating system.
The first computed example consists of finding the admissible permutations of the nodes of a modified star graph S n with data matrix (4.5 the Laplacian of the similarity matrix associated to the graph has a double Fiedler value equal to 1. Since an orthogonal basis for the eigenspace F corresponding to the Fiedler value is known, every x ∈ F can be expressed by x = Q 2 y, with y = [α, β] T , as in (4.8). As explained in detail in Section 4.1, the permutations of the nodes that yield a solution to the seriation problem are given by all the possible reorderings of the entries of x.
The results of the experiments concerning the application of the graphical and the Monte Carlo methods to a graph S n with a number of nodes n ranging from 5 to 10 are displayed in Table 6.1. In particular, the second column contains the number 3(n − 2)! of admissible permutations for a modified star graph stated in (4.15). It coincides with the number of admissible permutations found by the graphical method, reported in the third column of the table. We note that such number is one half of the estimate furnished by Equation (3.2), for k = 2. For the following examples, the reduction with respect to this estimate is even larger.
As the fifth column shows, the Monte Carlo method fails to identify all the permutations, after considering N = 1000 random linear combinations of the orthonormal basis for the eigenspace F . We verified that increasing the value of N up to 5000 the performance of the method does not improve. In this test, the graphical algorithm is, for every n, much faster than the Monte Carlo method, as one can observe comparing the computing time in seconds reported in the fourth and sixth columns of Table 6.1.
We remark that the failure of the Monte Carlo approach is due to the fact that many admissible permutations result from specific values of the coefficients α and β in the linear combination (4.8); see, e.g., (4.14). Assuming such values is an event with zero probability in a random draw of real numbers, so it is very unlikely to occur in the algorithm. On the contrary, the graphical method explicitly considers equal components in the Fiedler vectors when it processes intersections between the lines; see lines 23 and 27 of Algorithm 1.
A similar comparison between the two methods has also been considered for the cycle graph C n analyzed in Section 4.2. The results are displayed in Table 6.2. In this case, every vector x in the eigenspace associated with the double Fiedler value of C n can be represented as in Equation (4.22). In Section 4.2, we have not been able to foresee the number of admissible permutations for this graph, but the result we found for n = 4, 5, 6, 7 are confirmed by the outcome of the graphical method; see the second column in Table 6.2. Again, the graphical method proves to be the fastest one and the Monte Carlo method fails in recovering all the admissible permutations. The reason for this failure is the same as discussed above. The results displayed in Table 6.3 are obtained by applying the two methods to the generalized Petersen graph GP G(n, 1). As discussed in Section 4.3, both the outer and the inner subgraphs in GP G(n, 1) are cycle graphs and the total number of nodes is 2n. By following the discussion regarding the cycle graph and the results contained in Theorem 4.7 and Corollary 4.8 it follows that each vector x in the eigenspace corresponding to the Fiedler value has n macronodes of size two. Then, keeping into account the number of permutations for a cycle, the admissible permutations of the nodes in GP G(n, 1) are at least 2 n n.
The second column of Table 6.3 reports this minimum value for the admissible permutations. It is remarkable to observe that this is exactly the number of permutations recovered by the Monte Carlo method. Anyway, the real number of admissible permutations is much larger than that, as testified by the results of the graphical method in the third column of the table. This huge number of permutations requires a large computing time, making the graphical method extremely slower than in the other examples. Nevertheless, it is effective when computing the complete solution of the problem, while the randomized approach it is not, even if in this case N = 5000 random Fiedler vectors have been used.
We analyzed the performance of both methods by means of the "profiler" available in Matlab. It turns out that the bottleneck for the execution time of the algorithms are the tests for verifying that a new permutation does not appear in the list of those already computed either in direct or reverse ordering. When the number of admissible permutations is not too large, this does not significantly affect the complexity of the graphical method, while it does in the case of the generalized Petersen graph. 7. Conclusions. In this paper we studied the possible orderings of the Fiedler vector of a graph, under the assumption that the Fiedler value has multiplicity larger than one. The determination of such ordering is related to the solution of the seriation problem. We showed that, in the special case of a double Fiedler value, the number of admissible permutations is smaller than the maximum number of permutations allowed. In fact, it depends on the structure of the underlying bipartite graph. We examined three case studies for which it is possible to draw conclusions about the solution of the problem, and we proposed a graphical method and a randomized algorithm to list the admissible permutations. Examples and numerical experiments illustrate the performance of the proposed methods on the analyzed case studies.