arXiv:1211.4520v2 [] 28 Apr 2013

Storing Cycles in Hopfield-type Networks with
Pseudoinverse Learning Rule: Admissibility and
Network Topology
Chuan Zhanga , Gerhard Dangelmayra , Iuliana Opreaa,∗
a

Department of Mathematics, Colorado State University, Fort Collins, CO 80523, USA

Abstract
Cyclic patterns of neuronal activity are ubiquitous in animal nervous systems,
and partially responsible for generating and controlling rhythmic movements
such as locomotion, respiration, swallowing and so on. Clarifying the role
of the network connectivities for generating cyclic patterns is fundamental
for understanding the generation of rhythmic movements. In this paper,
the storage of binary cycles in Hopfield-type and other neural networks is
investigated. We call a cycle defined by a binary matrix Σ admissible if a
connectivity matrix satisfying the cycle’s transition conditions exists, and if
so construct it using the pseudoinverse learning rule. Our main focus is on the
structural features of admissible cycles and the topology of the corresponding
networks. We show that Σ is admissible if and only if its discrete Fourier
transform contains exactly r = rank(Σ) nonzero columns. Based on the
decomposition of the rows of Σ into disjoint subsets corresponding to loops,
where a loop is defined by the set of all cyclic permutations of a row, cycles
are classified as simple cycles, and separable or inseparable composite cycles.
Simple cycles contain rows from one loop only, and the network topology is
a feedforward chain with feedback to one neuron if the loop-vectors in Σ are
cyclic permutations of each other. For special cases this topology simplifies
to a ring with only one feedback. Composite cycles contain rows from at
least two disjoint loops, and the neurons corresponding to the loop-vectors
in Σ from the same loop are identified with a cluster. Networks constructed
from separable composite cycles decompose into completely isolated clusters.
∗

Corresponding author
Email address: juliana@math.colostate.edu (Iuliana Oprea)

Preprint submitted to Neural Networks

January 26, 2018

For inseparable composite cycles at least two clusters are connected, and the
cluster-connectivity is related to the intersections of the spaces spanned by
the loop-vectors of the clusters. Simulations showing successfully retrieved
cycles in continuous-time Hopfield-type networks and in networks of spiking
neurons exhibiting up-down states are presented.
Keywords: Cyclic Patterns, Hopfield-type Networks, Pseudoinverse
Learning Rule, Admissibility, Network Topology
1. Introduction
Applications of artificial neural networks in content addressable (associative) memory have attracted much attention in the last few decades (Hopfield, 1982, 1984; Little, 1974; McEliece et al., 1987; Šı́ma & Orponen, 2003;
López-Rodrı́guez et al., 2005). Hopfield-type networks are among the most
popular models of artificial neural networks for studying content addressable memory. According to Hopfield’s original idea, the privileged regime to
store information has been fixed point attractors, however experiments (e.g.,
Korn & Faure, 2003) indicate that cycles are used to store information and
chaotic dynamics appears as the background regime composed of these cyclic
“memory bags”.
In general, the storage of pattern sequences is one of the most important
tasks in both biological and artificial intelligence systems. A sequence containing repetitions of the same subsequence is said to be complex (Guyon et
al., 1988; Wang & Arbib, 1990; Wang, 2003), and cyclic patterns (or cycles of
patterns) are one of the important classes of such sequences. In animal nervous systems, cyclic patterns of neuronal activity are ubiquitous and partially
responsible for generating and controlling rhythmic movements such as locomotion, respiration, swallowing and so on. Neural networks that can produce
cyclic patterned outputs without rhythmic sensory or central input are called
central pattern generators (CPGs). While in some lower level invertebrate
animals detailed connectivity diagrams among identified CPG neurons have
been experimentally determined, the anatomic structure of CPG networks
in most higher vertebrate animals including human beings remain largely
unknown (e.g., MacKay-Lyons, 2002; Marder et al., 2005; Selverston, 2010).
According to Yuste (Yuste, 2008), the network connectivity problem, i.e.
experimentally identifying the connectivity diagram of biological neural networks, is one of the four basic problems that have to be solved to fully
2

understand a biological neural network. However, recent experimental observations (e.g., Dickinson & Moulins, 1992; Meyrand et al., 1994) suggested
that CPGs may be highly flexible, some of them may even be temporarily formed only before the production of motor activity (Jean, 2001). This
makes experimentally identifying the architecture of CPGs very difficult. As
indirect approaches to solve the network connectivity problem, observable
movement features such as symmetry etc. have been used to infer aspects
of CPG structures (e.g. Golubitsky et al., 1999). In this paper, we study
the network connectivity problem for storing binary cyclic patterns. Given
an arbitrary binary cyclic pattern, we ask whether there exists a network
whose architecture allows to produce it, and if there exists one, then how the
cycle determines the network structure. While the main motivation for our
study is the storage of cycles in continuous-time Hopfield-type networks, this
question is independent of the specific dynamics of the individual neurons
the network is composed of.
In both discrete and continuous asymmetric variants of Hopfield-type
networks, the storage and retrieval of sequences including cycles of binary
patterns have been investigated (Personnaz et al., 1986; Guyon et al., 1988;
Gencic et al., 1990), and biologically plausible learning rules such as Hebb’s
rule, the pseudoinverse rule and their variants with and without delays have
been used. In this paper, we follow Gencic et al. (1990) and use continuoustime Hopfield-type networks as models to study the relation between cyclic
patterns and the architecture of the networks constructed from them. In
addition to the simple dynamics of single neurons, another advantage of
Hopfield-type networks is that they deal with binary states. In neurophysiology it is well known that both CPG neurons and cortical neurons show
bistable membrane behaviors, which are commonly referred to as plateau
potentials (e.g Straub et al., 2002; Grillner, 2003; Selverston, 2010) or updown states (e.g. Sanchez-Vives & McCormick, 2000; Cossart et al., 2003).
Accordingly, a sequence of the binary states +1 and −1 traversed by a single
neuron in a Hopfield-type network can be interpreted as a sequence of up
and down states, respectively.
While simulations of networks constructed using Hebbian learning rules
have been shown to be qualitatively consistent with experimental recordings (Kleinfeld & Sompolinsky, 1988), it is well known that Hopfield-type
networks with Hebbian learning rules do not perform well when the patterns to be stored are correlated which is usually the case in practice (Rojas,
1996). To avoid this problem, a pseudoinverse learning rule was introduced
3

by Amari (Amari, 1977), and in the Hopfield framework by Personnaz et al.
and Kanter et al. (Personnaz et al., 1986; Kanter & Sompolinsky, 1987).
It has been suggested that the pseudoinverse learning rule and its variants
may take key roles in the associative perception of human faces in the human
cortex (Zifan et al., 2007) and the encoding of location information in the rat
hippocampus (Marinaro et al., 2007). Recently, Tapson and Schaik proposed
an algorithm referred to as OPIUM (Online Pseudoinverse Update Method)
for computing the pseudoinverse, and showed that the pseudoinverse learning
rule is plausible as a physiological process in real neurons (Tapson & Schaik,
2013). Since the pseudoinverse method gives an exact solution of the network
connectivity problem if a solution exists (Personnaz et al., 1986), we use this
method to construct networks for storing binary cycles.
Although the pseudoinverse rule and its variants (Amari, 1977; Personnaz
et al., 1986) extend to more general cases, most investigations in discretetime Hopfield-type networks characterized or were implemented for cycles or
sequences of linearly independent patterns (e.g. Personnaz et al., 1986; Kanter & Sompolinsky, 1987). An approach to storing cycles of correlated as
well as linearly independent patterns in continuous-time Hopfield-type networks has been proposed by Gencic et al. (1990). In this study, a successfully
retrieved cycle is revealed as an attracting limit cycle in the network dynamics, but the question for which cycles the corresponding network connectivity
problem admits a solution was not addressed.
In our study, a cycle is defined by a N × p-matrix, Σ, of binary states,
where N is the number of neurons in the network and p is the length of
the cycle. The network connectivity problem associated with a cycle Σ can
be formulated as follows: Find a real N × N -matrix J such that JΣ = F ,
where F is related to Σ by a cyclic permutation of the columns. The main
objective of this paper is to study the existence and properties of solutions of
this equation along with the structural features of the corresponding cycles,
and the network topologies associated with them. If a solution J exists, we
call the cycle Σ admissible and construct J using the pseudoinverse method.
While the main motivation for our study is the storage of binary cycles in
continuous-time Hopfield-type neural networks, the question whether a given
cycle is admissible is independent of the particular network-model. For the
discrete-time Hopfield-type networks studied by Personnaz et al. (1986) and
Guyon et al. (1988), J can be used directly as connectivity matrix. For the
continuous-time Hopfield-type networks considered in Section 2.1, we follow
the approach of Gencic et al. (1990) and represent the connectivity matrix
4

as a weighted sum of J and another matrix J0 , that serves to store the
individual patterns in Σ as fixed points. To demonstrate that our approach
also works for more complicated neuron-models, we introduce in Section 2.2
a single-compartment neuron model that exhibits up-down states and show
an example of a successfully retrieved cycle.
Our main objective is to analyze and classify the structural features of
admissable cycles Σ and the topology of the networks constructed from them.
A basic result is that if and only if the discrete Fourier transform of Σ contains
exactly r = rank(Σ) nonzero columns, then Σ is admissible.
Our approach to classify cycles is based on the decomposition of the row
vectors of Σ into disjoint subsets corresponding to different loops created by
cyclic permutations of the rows. If the cycle is admissible, each of these loops
is associated with an invariant subspace of the row space, U, of Σ under cyclic
permutations. This row-decomposition leads naturally to a classification of
cycles into simple cycles, separable composite cycles, and inseparable composite cycles. Simple cycles contain rows from a single loop only. Composite
cycles contain rows from at least two disjoint loops, and for each loop the
neurons corresponding to the loop vectors in Σ are identified with a cluster, which in turn corresponds to an indecomposable invariant subspace of
U under cyclic permutations if Σ is admissible. Two clusters are directly
connected if their subspaces intersect nontrivially, and they are connected if
they are part of a chain of directly connected clusters. A network constructed
from a simple admissible cycle has only one cluster, and we show that the
network topology is a feedforward chain with feedback to one neuron if the
loop vectors in Σ are all cyclic permutations of each other. For special simple
cycles, there is only one feedback and the network topology simplifies to a
ring. Networks constructed from separable composite cycles decompose into
completely isolated clusters.
The paper is organized as follows. In Section 2, the pseudoinverse learning rule is introduced in the framework of continuous-time Hopfield-type networks. Additionally, in order to demonstrate that the pseudoinverse learning rule can be applied to other networks as well, networks of spiking neurons with plateau membrane potentials and postinhibitory rebound are introduced, and simulations showing the successful retrieval of a prescribed cycle
are presented. In Section 3, the general admissibility criterion in terms of
the discrete Fourier transform of the cycle matrix is formulated and proved,
and the relation of admissible cycles with cyclic permutation groups is discussed. Based on the structural features of the invariant subspaces of the row
5

space of an admissible cycle, in Section 4, admissible cycles are classified into
simple cycles, and separable and inseparable composite cycles, and for each
type of cycles a corresponding admissibility condition is derived. In Section
5, the topologies of networks constructed from different types of admissible
cycles are studied, and in Section 6 implications of the results presented in
this paper are discussed.
2. Pseudoinverse Learning Rule and Neural Networks
2.1. Hopfield-type Neural Networks
A continuous-time Hopfield-type network (Hopfield, 1984) is described
by a system of ordinary differential equations for ui (t), 1 ≤ i ≤ N , which
model the membrane potential of the i-th neuron in the network at time t.
Assuming that all neurons are identical, normalizing the neuron amplifier
input capacitance and resistance to unity and neglecting external inputs, the
governing equations are,
N

X
dui
= −ui +
J˜ij vj , 1 ≤ i ≤ N,
dt
j=1

(1)

where vj (t) is the firing rate of the j-th neuron and J̃ = (J˜ij )N ×N is the
connectivity matrix. The firing rate vj is related to the membrane potential
uj through a sigmoid-shaped gain function, vj = g(uj ), which we choose,
following Hopfield (1984), as g(uj ) = tanh(λuj ), where λ controls the steepness. Using vector notation, u = (u1 , . . . , uN )T , v = (v1 , . . . , vN )T , (1) can
be more compactly written as (dots denote time derivatives)
u̇ = −u + J̃ tanh(λu),

(2)

where here and subsequently a scalar function applied to a vector or matrix denotes the vector or matrix obtained by applying the function to each
component, i.e.
tanh(λu) = (tanh(λu1 ), tanh(λu2 ), . . . , tanh(λuN ))T .
Alternatively, since uj = arctanh(vj )/λ, (2) can be rewritten as a system of
differential equations for the firing rates,
v̇ = λ(I − diag(v2 ))(J̃v −
6

arctanh(v)
),
λ

(3)

where I is the N × N identity matrix.
In this paper we study the structure of binary pattern cycles that can be
stored in the network modeled by the above autonomous system. Following
Hopfield (1982, 1984), any N -dimensional {−1, 1}-valued column vector is
identified with a binary vector or pattern, and we use + and − to denote 1
and −1.
Personnaz et al. (1986) and Guyon et al. (1988) studied the storage of
sequences of patterns in discrete-time Hopfield-type networks. A sequence of
(µ) (µ)
(µ)
(µ)
p patterns ξ (µ) = (ξ1 , ξ2 , . . . , ξN )T , 1 ≤ µ ≤ p, ξi = + or −, is defined
by p transition conditions ξ (µ) → f (µ) , where f (µ) is one of the given vectors,
i.e., f (µ) ∈ {ξ (1) , . . . , ξ (p) } for each µ. Thus a sequence is characterized by
two N × p-matrices Σ = (ξ (1) , . . . , ξ (p) ) and F = (f (1) , . . . , f (p) ). The two
matrices are related to each other by the transition conditions, which can be
conveniently formulated in terms of a p × p transition matrix as F = ΣP,
where Pνµ = 1 if f (µ) = ξ (ν) and 0 otherwise. For example, for p = 3
and the simplest case of a sequence starting at ξ (1) and terminating at ξ (3) ,
ξ (1) → ξ (2) , ξ (2) → ξ (3) , ξ (3) → ξ (3) , we have F = (ξ (2) , ξ (3) , ξ (3) ) and P is
singular, but the general definition in terms of Σ and F allows to consider
more complex as well as multiple sequences. Personnaz et al. (1986) showed
that the storage of such a sequence leads to the matrix equation,
JΣ = F,

(4)

for the connectivity matrix J of the discrete network. It was pointed out by
Personnaz et al. (1986), that, if F Σ+ Σ = F , where Σ+ is the Moore-Penrose
pseudoinverse of Σ, then (4) has the exact solution J = F Σ+ , which was
called associating learning rule by these authors.
A cycle of p patterns is a sequence with F = (ξ (2) , ξ (3) , . . . , ξ (p) , ξ (1) ), i.e.,
ξ (µ) → ξ (µ+1) for µ < p and ξ (p) → ξ (1) , and the corresponding transition
matrix is


0 0 0 ··· 0 1
 1 0 0 ··· 0 0 


 0 1 0 ··· 0 0 


P =  .. .. .. . . .. ..  .
(5)
 . . .
. . . 


 0 0 0 ··· 0 0 
0 0 0 ··· 1 0
We are interested in the storage of cycles in the continuous-time Hopfield
networks defined by (2). Our approach to compute a connectivity matrix J̃
7

for this purpose follows Gencic et al. (1990). In this paper, the connectivity
matrix J̃ is decomposed as
J̃ = βK (C0 J0 + C1 J),

(6)

where J0 serves to stabilize the network in its current memory state and J
imposes the transitions between the memory states. Here, C1 = 1 − C0 and
C0 , 0 ≤ C0 ≤ 1, control the relative contributions of the two components of
J̃. The fixed point condition is realized by requiring that v = β1 ξ (µ) , with a
parameter 0 < β1 < 1, is a fixed point if C0 = 1. Noting that arctanh(x) is
(µ)
an odd function and |ξi | = 1, this leads, according to (3), to the condition
J̃β1 ξ (µ) =

1
1
arctanh(β1 ξ (µ) ) = arctanh(β1 )ξ (µ) ,
λ
λ

for every µ, hence J̃Σ = βK Σ with βK =

1
arctanh(β1 ), which has the
λβ1

solution J̃ = βK J0 with
J0 = ΣΣ+ .

(7)

Regarding the transition conditions, we stipulate that v(t) = β1 ξ (µ) implies
v(t + τ ) = β1 f (µ) for some τ , and require accordingly for C0 = 0 that
J̃Σ = βK F . This leads to equation (4), which in terms of the transition
matrix P, equation (5), becomes
JΣ = ΣP.

(8)

According to the associating learning rule of Personnaz et al. (1986), (8) has
the solution
J = ΣPΣ+ ,
(9)
provided that ΣPΣ+ Σ = ΣP. If this condition is not satisfied, (8) has no
solution.
The main objective of this paper is the study of the existence and properties of the solutions of (8) along with the structural features of the corresponding cycles, and the network topologies resulting from J0 and J defined
by (7) and (9). A bifurcation analysis and a study of the dynamics of (2) with
(6), with C0 and β = λβK > 1 treated as parameters, are given elsewhere,
where we also consider the extension of (2) to a dynamical system with a
delay,
u̇ = −u + C0 βK J0 tanh(λu) + C1 βK J tanh(λuτ ),
(10)
8

Figure 1: A successfully retrieved cycle Σ (see text for details) in a network of three
neurons. A shows the firing rates vi (t) of the three neurons and the raster plot B shows
the overlaps m(ν) (t), which measure the similarity of the network state v(t) with each of
the six patterns in the cycle (see text). C illustrates the retrieval of the cycle in the phase
space of the system.

with a delay-time τ > 0 and uτ (t) = u(t − τ ). Here we show only one
example of a successfully retrieved cycle for (2), a network of N = 3 neurons.
The cycle consists of six states, Σ = (ξ (1) , . . . , ξ (6) ), with ξ (1) = (+, +, +)T ,
ξ (2) = (+, +, −)T , ξ (3) = (+, −, −)T and ξ (3+µ) = −ξ (µ) for µ = 1, 2, 3. The
retrieval of the cycle is illustrated in Figure 1. The raster plot B in this
figure shows the overlaps, defined in general as
N
1 X
(ν)
vi (t)ξi , 1 ≤ ν ≤ p,
m (t) =
N i=1
(ν)

(11)

of the actual network state v(t) with the patterns of the cycle. The overlap
m(ν) (t) is a normalized measure of the similarity of v(t) with ξ (ν) . Maximal
similarity with ξ (ν) and −ξ (ν) occurs for m(ν) close to 1 and −1, respectively.
The raster plot of the overlaps in Figure 1B as well as the time series in Figure
1A clearly illustrate that the cycle is retrieved successfully. The parameters
C0 and β used in this simulation were C0 = 0.6 and β = 4.
2.2. Networks of Spiking Neurons
As was pointed out in the introduction, although our results are developed
in the framework of Hopfield-type networks, they also can be used to store
cycles in other neural networks. In this subsection, we introduce a network
9

model of identical spiking neurons with bistable membrane behavior and
postinhibitory rebound, and show an example of a successfully retrieved cycle
in a network constructed using the pseudoinverse method.
We consider the simplest single-compartment neuron model, the passive
integrate-and-fire (PIF) model (Dayan & Abbott, 2001; Parga & Abbott,
2007). The model is described by the following first-order nonlinear ordinary
differential equation,
cm

dVi
(i)
(i)
(i)
(i)
= −IL (t) − Inl (t) + IsynE
(t) + IsynI
(t),
dt

(12)

where Vi (t) is the membrane potential of the i-th neuron in the network, and
if Vi (t) ≥ θ where θ = −45mV is the threshold for the firing action potentials,
then Vi (t + dt) = 0, and Vi (t + 2dt) = Vreset with dt = 0.005ms and Vreset =
−55mV. After each action potential, an absolute refractory period tRef r =
1ms is imposed, and during the refractory period the membrane potential
Vi (t) is fixed at Vreset . The parameter cm , chosen as cm = 20nF/mm2 , is the
specific membrane capacitance. The membrane and synaptic currents of the
i-th neuron are respectively given as follows.
Leakage membrane current:
(i)

IL (t) = gL (Vi (t) − EL ),

(13)

where gL = 1µS/mm2 and EL = −68mV.
Nonlinear membrane current:
(i)

Inl (t) = gnl (Vi (t) − E1 )(Vi (t) − E2 )(Vi (t) − E3 ) − δ,

(14)

where gnl = 0.03mV−2 , E1 = −72mV, E2 = −58mV, E3 = −44mV and δ
is a parameter for shifting the nonlinear membrane current to control the
stability of the up state. In the simulation shown in the paper, we chose
δ = −31.685.
Excitatory synaptic current:
(i)
IsynE
(t) = ḡsynE si (t)(Vi (t) − EsynE ),

(15)

where ḡsynE = 68µS/mm2 , EsynE = −120mV, and the activation variable
si (t) satisfies the following first order differential equation,
N


X
dsi
= αE si − 10
Θ(Jij )Jij Θ(Vj (t − τ ) − Vthr ) ,
dt
j=1

10

(16)

where αE = 1, Vthr = −45mV, τ = 10ms, Θ(x) is the Heaviside step function,
and the Jij are the components of the connectivity matrix J.
Inhibitory synaptic current:
(i)
IsynI
(t) = ḡsynI zi (t)(Vi (t) − EsynI ),

(17)

where ḡsynI = 118µS/mm2 , EsynI = −120mV, and the activation variable is
given by zi (t) = (xi (t) + yi (t))/2, with xi (t) and yi (t) satisfying the following
first order differential equations,
N


X
dxi
= αI xi − 10
Θ(−Jij )Jij Θ(Vj (t − τ ) − Vthr ) ,
dt
j=1
N


X
dyi
= βI yi + 10
Θ(−Jij )Jij Θ(Vj (t − τ ) − Vthr ) ,
dt
j=1

(18)

with αI = 2, βI = 0.08, and τ = 10ms.
With the parameters of a single neuron fixed as above, the dynamics of
a network of N PIF-neurons is fully determined by the connectivity matrix
J. We constructed J from prescribed cycles using the pseudoinverse learning
rule J = ΣPΣ+ , i.e. without invoking a fixed point condition. Figure 2
illustrates a successfully retrieved 6 × 8 cycle Σ. The first four rows of Σ
are σ1 Pj−1 , j = 1, 2, 3, 4, and the last two rows are σ2 and σ2 P, where
σ1 = (+, +, +, +, −, −, −, −) and σ2 = (+, +, −, −, +, +, −, −).
Figure 2A shows the retrieved traces of the membrane potentials Vi (t)
of the six neurons in the network. Since the firing rates are not included
as variables in the model, they have to be extracted from the time series.
Following Dayan & Abbott (2001), we counted for given t the number of
times t0 within the time window t − ∆t/2 ≤ t0 ≤ t + ∆t/2 at which neuron
i fired, and divided this number by ∆t. The resulting function, Ri (t), is
considered as an approximation of the firing rate of the i-th neuron. For
∆t we chose ∆t = 5ms. We also introduce the normalized firing rates,
vi (t) = 2Ri (t)/ max Ri (t) − 1 (so that −1 ≤ vi (t) ≤ 1, analogous to the
firing rates used in continuous-time Hopfield-type networks), and define the
overlaps m(ν) (t) as in equation (11).
To compare the membrane potentials with the prescribed cycle, we extracted the time spans between the first spike and the last spike in each
up-state, and identified their average divided by 4 as the time span for each
binary state. The resulting time span is 11.3ms and is slightly larger than
11

Figure 2: Successful retrieval of a cycle Σ with eight states prescribed in a network of six
spiking neurons with the pseudoinverse learning rule. A: membrane potential, B: Firing
rates, and C: Overlaps (see text for details).

the time-delay τ = 10ms in the synaptic couplings. In Figure 2A, the gray
strips in the background indicate these time spans, and the dark gray +’s
and −’s label the corresponding binary states in the prescribed cycle. The
firing rates Ri (t) and the overlaps m(ν) (t) are displayed in Figure 2B and C,
respectively. The black arrows in A, B, and C indicate the time span when
the first binary pattern, ξ (1) = (+, +, +, +, +, +)T , in the prescribed cycle is
retrieved for the first time in the displayed time range. The plots in Figure
2 clearly demonstrate that the cycle is retrieved successfully.
Other cycles were retrieved successfully as well, but in contrast to continuous time Hopfield-type networks, especially with delayed couplings, we
observed in simulations that some prescribed cycles are difficult to be retrieved in networks of the spiking neurons introduced in this subsection.
This is likely because of the complicated dynamics of the individual neurons,
which makes the appropriate choice of parameter values more difficult. In
general, especially in physiologically based neural network models, the neuronal dynamics may take key roles in shaping the dynamics of the networks,
and reinforce or weaken the contribution of the network structure in reproducing prescribed cycles. In this case, it is important to find out whether a
cyclic patterned output in a system arises from a network-based mechanism
or not, and if it does, then to which extent and how the cyclic patterned
output is determined by the network architecture.
In the next three sections, without considering the specific dynamics of
12

single neurons, we formulate and prove conditions for any cyclic pattern
under which a connectivity matrix in accordance with the cycle’s transition
conditions can be constructed, and for cycles for which this is the case we
analyze and classify their structural features and their relation to the network
topology.
3. Admissible Cycles and Cyclic Permutation Groups
Definition 1. Let P be the cyclic p × p-permutation matrix defined in (5).
A cycle defined by a binary N × p-matrix Σ = (ξ (1) , ξ (2) , . . . , ξ (p) ) is said to
be admissible, if there is a real N × N matrix J such that equation (8) is
satisfied.
Note that if Σ is admissible, the solution to (8) may be not unique. If
there are several solutions, we select (9) as distinguished solution because of
its close relationship to J0 , see Remark 1(b) below.
Gencic et al. (1990) consider a special type of cycles defined by p binary
vectors Σ0 = (ξ (1) , ξ (2) , . . . , ξ (p) ), which satisfy the transition condition ξ (1) →
ξ (2) → · · · ξ (p) → −ξ (1) → −ξ (2) → · · ·−ξ (p) → ξ (1) . In this paper we consider
these cycles as special cases of cycles of period 2p with Σ = (Σ0 , −Σ0 ).
For storing sequences, Personnaz et al. (1986) pointed out that, if the
associating learning rule F Σ+ Σ = F is satisfied, the rows of F are linear
combinations of the rows of Σ. This follows from the fact that Σ+ Σ is
the orthogonal projection matrix onto the subspace of Rp spanned by the
rows of Σ. For storing single cycles, their conclusion can be reformulated
geometrically as follows:
Proposition 1. A cycle Σ of size N × p is admissible, if and only if its row
space is invariant under P, i.e.
span{R(Σ)} = span{R(ΣP)},

(19)

where R(Σ) denotes the set of all row vectors of Σ.
Note that |R(Σ)| ≤ N , and if |R(Σ)| < N then two or more different rows
of Σ are identical, that is, the corresponding neurons traverse the same cycle.
Although this is a kind of redundancy, we do not exclude this possibility in
our general discussion.
We next formulate a useful alternative admissibility criterion involving
the eigenspaces of P. Since P is a circulant matrix, P has the orthogonal
eigenvectors v (k) = (1, ρk , ρ2k , . . . , ρ(p−1)k )T for 0 ≤ k < p, where ρ = e2πi/p
13

√
(i = −1) is the basic primitive p-th root of unity (Lancaster & Tismenetsky, 1985), and in this special case the eigenvalues are ρ̄k . We set
V = (v (0) , v (1) , . . . , v (p−1) ), λj = ρ̄j−1 (1 ≤ j ≤ p), Λ = diag(λ1 , . . . , λp ) and
note that P = V ΛV −1 with V −1 = V ∗ /p, where here and subsequently complex conjugation is marked by an overbar and an asterisk denotes the adjoint
(complex conjugate transpose) matrix or vector.
Since the transition matrix P leaves its eigenspaces invariant, it follows
that if the row space of Σ coincides with the direct sum of its projections
onto the eigenspaces of P, then Σ is admissible. Based on this consideration,
we obtain the following admissibility criterion.
Theorem 1. Let Σ be a cycle whose matrix form is of size N × p, and let
Σ̂ = ΣV . Then Σ is admissible, if and only if Σ̂ has precisely r nonzero
columns, where r = rank(Σ) = rank(Σ̂).
Proof. Noting that JΣ = ΣP = ΣV ΛV −1 implies JΣ̂ = Σ̂Λ, it follows that
Σ is admissible if and only if there exists an N × N -matrix J such that
JΣ̂ = Σ̂Λ,

(20)

Jcolj (Σ̂) = λj colj (Σ̂), 1 ≤ j ≤ p,

(21)

which implies
where colj (Σ̂) denotes the j-th column of Σ̂.
Suppose now that Σ is admissible and rank(Σ) = r. Since the columns
of V consist of eigenvectors associated to distinct eigenvalues of P, it follows
that Σ̂ = ΣV has r linearly independent columns. Assume colµ1 (Σ̂), . . . , colµr (Σ̂)
are linearly independent. Then (21) implies that λµ1 , . . . , λµr are eigenvalues
of J and colµ1 (Σ̂), . . . , colµr (Σ̂) are the corresponding eigenvectors. If Σ̂ has
an additional nonzero column, colj (Σ̂), with j ∈
/ {µ1 , . . . , µr }, then by (21)
this column is an eigenvector of J corresponding to the eigenvalue λj and
λj 6= λµi for 1 ≤ i ≤ r. On the other hand, colj (Σ̂) is a linear combination of
colµ1 (Σ̂), . . . , colµr (Σ̂) which is impossible, since eigenvectors corresponding
to different eigenvalues are linearly independent. Thus all columns except
colµ1 (Σ̂), . . . , colµr (Σ̂) must be zero.
Conversely, assume Σ̂ has r nonzero columns colµ1 (Σ̂), . . . , colµr (Σ̂) and
all other columns of Σ̂ are zero. Since rank(Σ̂) = r, these columns are linearly
independent. Let Q be a p × p permutation matrix that maps the column j

14

to the column µj for 1 ≤ j ≤ r. Then
Σ̂ = [0, . . . , 0, colµ1 (Σ̂), 0, . . . , 0, colµr (Σ̂), 0, . . . , 0]
= [colµ1 (Σ̂), . . . , colµr (Σ̂), 0, . . . , 0]Q.
Let Σ̂0 = [colµ1 (Σ̂), . . . , colµr (Σ̂)] and Σ̂∗0 be the adjoint (complex conjugate
transpose) matrix of Σ̂0 and define


(Σ̂∗0 Σ̂0 )−1 Σ̂∗0
T
J = Σ̂ΛQ
.
O(p−r)×N
Then
JΣ̂ =
=
=
=


(Σ̂∗0 Σ̂0 )−1 Σ̂∗0
Σ̂ΛQ
[Σ̂0 , ON ×(p−r) ]Q
O
(p−r)×N


Ir×r
Or×(p−r)
T
Σ̂ΛQ
Q
O(p−r)×r O(p−r)×(p−r)
Σ̂Λdiag(s1 , . . . , sp )
Σ̂Λ.
T



where Ir×r is the identity matrix of size r × r, Om×n is zero matrix of size
m × n, and
(
1, ifj ∈ {µ1 , . . . , µr }
sj =
.
0, ifj ∈
/ {µ1 , . . . , µr }

Remark 1. A group theoretical interpretation of admissible cycles Σ and
the associated matrices J0 and J can be given as follows:
(a) We denote by Zp the cyclic group of order p defined by addition of integers
modulo p. Viewed as permutation group, the generator of Zp , addition by 1
mod p, corresponds to the cyclic permutation {0, 1, . . . , p−1} → {1, 2, . . . , p−
1, 0}, and the matrix P is an orthogonal representation of this generator in
Rp or Cp that cyclically permutes row vectors to the left. Accordingly, the
matrices Pk , 0 ≤ k < p, form a p-dimensional representation of Zp with
Pp = I, the p × p identity matrix.
(b) The admissibility condition span{R(Σ)} = span{R(ΣP)} means that the
rows of Σ span a subspace of Rp or Cp that is invariant under P, and hence
under the full representation of Zp , that is,
span{R(Σ)} = span{R(ΣPk )}, 0 ≤ k < p.
15

Moreover, with J = ΣPΣ+ and ΣPΣ+ Σ = ΣP, we find that J2 = ΣP2 Σ+
and inductively
Jk = ΣPk Σ+ , 0 ≤ k < p,
(22)
which shows that Jp = ΣΣ+ = J0 and Jk Σ = ΣPk for 0 ≤ k < p. This means
that J restricted to the column space span{C(Σ)}, where C(Σ) denotes the
set of column vectors of Σ, generates a representation of Zp in this subspace
of RN . We also note that J0 is the orthogonal projection onto span{C(Σ)},
and
J0 Jk = Jk J0 = Jk ,
(23)
for all 0 ≤ k < p, which is a straightforward consequence of the basic properties ΣΣ+ Σ = Σ and Σ+ ΣΣ+ = Σ+ of the pseudoinverse and (22). Clearly,
the ranks of J, J0 and Σ coincide and are equal to the dimensions of the
vector spaces span{C(Σ)} and span{R(Σ)} in which Zp acts with matrix
generators J and P, respectively.
(c) The group Zp has exactly p irreducible complex representations which
are all one-dimensional and are generated by multiplication of a complex
number by ρ̄k , 0 ≤ k < p (Miller, 1972). When restricted to real spaces and
ρk ∈
/ R, the multiplications by ρ̄k and ρk = ρ̄p−k can be combined to form a
two-dimensional real irreducible representation space, in which the generator
of Zp acts by rotation of vectors by the angle 2πk/p. For the representation
of Zp in the full space of p-dimensional row vectors generated by P, the rows
in V ∗ are (complex) basis vectors for these irreducible subspaces, and those
basis vectors with eigenvalues ρ̄k for which Σ̂ has a nonzero column span
the irreducible subspaces in span{R(Σ)}. (Real bases in case of ρ̄k ∈
/ R are
obtained by taking real and imaginary parts of these vectors, but we prefer
to use the complex basis vectors.) Likewise, the non-zero columns of Σ̂ form
complex bases of the irreducible subspaces of the Zp -representation generated
by J in span{C(Σ)}. We note that, given a row-vector x ∈ Cp , xV is the
discrete Fourier transform of x, and the components of xV are the expansion
coefficients of x represented by the basis vectors in V ∗ /p.
Closely related to the group Zp are the p-th roots of unity, which in turn
are intimately related to the cyclotomic polynomials. In Sections 3-5 we
will make some use of these polynomials and therefore summarize their basic
properties in the appendix.
(d) Given a row-vector x ∈ Rp , the orbit of x under P is defined as the the set
{x, xP, . . . , xPp−1 }. For generic x ∈ Rp , this set is a basis of Rp , however the
set of binary row vectors, x = η, is finite and the orbit of η, which we call a
16

loop, may span only a proper subspace of Rp . In the next section we classify
(admissible) cycles according to the decomposition of R(Σ) into sets of rows
belonging to different loops. To pursue this, we will introduce a concept of
irreducibility that differs from the standard group-theoretical version above.
4. Classification of Cycles
4.1. Simple Cycles
Definition 2. Let η = (η 1 , η 2 , . . . , η p ) be a p-dimensional binary row vector.
The set
{ην : ην = ηPν , ν = 0, 1, 2, . . . , p − 1},
is called a loop and is denoted by Lη .
Remark 2. For any loop Lη , |Lη | ≤ p. More precisely, |Lη | = m, where m
is a factor of p. In particular, if η = (+, +, . . . , +), then |Lη | = 1, as ηP = η.
Definition 3. A cycle Σ is called simple, if its row vectors are from a loop
generated by some row vector η, i.e.,
R(Σ) ⊆ Lη .

(24)

A cycle Σ is composite, if it is not simple.
Definition 4. Let Σ be a cycle. The set GΣ = {η1 , η2 , . . . , ηq } is said to be
a generator of Σ, if
Lηi ∩ Lηj = ∅, ∀i =
6 j,
(25)
and
GΣ = {η1 , η2 , . . . , ηq } ⊆ R(Σ) ⊆

q
[

Lηi .

(26)

i=1

Note that any vector in Lηi ∩ R(Σ) can be chosen as generator instead of
ηi in GΣ , that is, the generators are unique up to cyclic permutations and
the condition to be vectors in R(Σ). In particular, for simple cycles there is
only one generator, |GΣ | = 1, and every row in R(Σ) can be chosen for this
generator. A simple criterion for admissibility is the following.
Proposition 2. A cycle Σ is admissible if Lη ⊂ span{R(Σ) ∩ Lη } for every
η ∈ GΣ .

17

Proof. This follows immediately from the fact that, under the given hypothesis, every row in R(ΣP) can be represented as linear combination of a subset
of rows in R(Σ).
Definition 5. Let η be any row vector. The rank of η is defined as the dimension of the vector space spanned by the row vectors in the loop generated
by η, i.e.,
rank(η) = dim span{Lη }.
(27)
Theorem 2. Let Σ be a simple cycle generated by η, i.e., η ∈ R(Σ) ⊆ Lη .
Then Σ is admissible, if and only if
rank(Σ) = rank(η).

(28)

Proof. Suppose rank(Σ) = rank(η). Then span{R(Σ)} = span{Lη } as R(Σ) ⊆
Lη . Since P is nonsingular and Lη P = Lη , it follows that span{R(ΣP)} =
span{Lη }, hence Σ is admissible. Conversely, suppose that Σ is admissible, i.e. span{R(Σ)} = span{R(ΣPm )} for all m ∈ N. Assume rank(Σ) <
rank(η). Then there exists η̂ ∈ Lη with η̂ ∈
/ span{R(Σ)}. Let η̂ = ηPµ for
some 0 < µ < p. Since η ∈ R(Σ), it follows that
η̂ ∈ R(ΣPµ ) ⊂ span{R(ΣPµ )} = span{R(Σ)},
which contradicts η̂ ∈
/ span{R(Σ)}.
Remark 3. In general, although P preserves the rank of any cycle Σ, the
vector space spanned by the row vectors of Σ may not be invariant under
P. For simple cycles, the condition (28) guarantees that the vector space
spanned by the rows of Σ is invariant under P, and hence guarantees the
admissibility of Σ. The condition (28) will be referred to as admissibility
condition for simple cycles.
4.2. Separable Composite Cycles
In order to generalize the class of simple admissible cycles to the class of
separable composite cycles, we first introduce the concept of decomposability
of the row space of a cycle into irreducible subspaces.
Definition 6. Let Σ be an admissible cycle of period p, and let U =
span{R(Σ)}. Note that admissibility implies UP = U, i.e. U is invariant under P. Let V ⊆ U be a subspace of U and assume VP = V and
R(Σ) ∩ V 6= ∅. Then
18

(a) The subspace V is called reducible if there exists a proper subspace W of
V such that WP = W and R(Σ) ∩ W 6= ∅.
(b) The subspace V is said to be decomposable, if V has the direct sum
decomposition
V = V1 ⊕ V2 ⊕ · · · ⊕ Vn ,
(29)
where n ≥ 2, Vi is invariant under P and Vi ∩ R(Σ) 6= ∅ for every 1 ≤ i ≤
n. The subspace V is said to be indecomposable, if it is not decomposable.
If Vi in (29) is indecomposable for every i, then (29) is called a complete
decomposition of V.
(c) The vector space U is called semisimple, if U is the direct sum of irreducible subspaces in the sense of (a). Note that semisimplicity of U includes
the case where U is irreducible, in which case we call U simple.
Remark 4. We emphasize that, because our purpose is to study the structure of the invariant subspaces spanned by the row vectors of Σ, the concepts
of reducibility and decomposability introduced in Definition 6 are slightly different from the standard definitions used in the representation theory of finite
groups (we require that each subspace contains a row vector of Σ). An irreducible/indecomposable invariant subspace in the sense of Definition 6 may
be reducible/decomposable in terms of the standard definitions of representation theory applied to the cyclic group Zp generated by P.
It is clear that if Σ is simple and admissible, then U is simple and consequently indecomposable, as η ∈ Ui implies that ηPk ∈ Ui for every k ∈ N.
However, the converse is not necessarily true. In the next example, we show
that the vector space spanned by the row vectors of a composite cycle may
be reducible but not decomposable.
Example 1. Consider


+
 +
Σ=
 +
+

+
+
−
−

+
−
−
+

−
−
−
−

−
−
+
+


−
+ 
,
+ 
−

and let ηj = rowj (Σ). Clearly, Σ is a composite cycle, as it is generated by
{η1 , η4 }. Let U = span{R(Σ)}, U1 = span{Lη1 } and U2 = span{Lη4 }. Since
η4 = η1 − η2 + η3 , i.e. η4 ∈ U1 , we have that U2 ⊂ U1 = U. Moreover,
R(ΣP) = {η2 , η3 , −η1 , −η4 } implies UP = U, hence Σ is admissible. Since
both U1 and U2 are invariant under P it follows that U is reducible, however,
U is not decomposable.
19

Proposition 3. Let Σ be an admissible cycle with generator GΣ = {η1 , . . . , ηq }.
Assume U = span{R(Σ)} is semisimple and let U = U1 ⊕ U2 ⊕ · · · ⊕ Un be a
decomposition of U into irreducible subspaces. Then n ≤ q and there exists
a subset {i1 , . . . , in } ⊆ {1, . . . , q} such that Uj = span{Lηij } for 1 ≤ j ≤ n.
Moreover, if span{Lηi } =
6 span{Lηj } for every i, j ∈ {1, . . . , q} with i 6= j,
then n = q.
Proof. Let η ∈ GΣ and let V ∈ {Uj |1 ≤ j ≤ n} be the subspace in the
decomposition of U that contains η. Invariance of V implies ηP ∈ V, hence
ηP2 ∈ V and by induction Lη ⊂ V, thus span{Lη } ⊂ V. Since span{Lη }
is invariant, span{Lη } ∩ R(Σ) 6= ∅ and V is irreducible, it follows that V =
span{Lη }, and there exists no η 0 ∈ GΣ , η 0 6= η, such that span{Lη0 } is
a proper subspace of span{Lη } and vice versa. Thus, for i 6= j, either
span{Lηi } ∩ span{Lηj } = {0} or span{Lηi } = span{Lηj }. It follows that
there exists i1 , . . . , in ∈ {1, . . . , q}, ij 6= ik if j 6= k, such that
span{R(Σ)} = span{

q
[

Lηi } =

i=1

n
M

span{Lηij }.

j=1

Example 2. Let η1 = (+, +, −, +, +, −), η2 = −η1 and η3 = (+, +, +, −, −, −).
Let Σ be the 9 × 6-cycle defined by
Σ = (ΣT1 , ΣT2 , ΣT3 )T ,
where Σj = (ηjT , (ηj P)T , (ηj P2 )T )T for j = 1, 2, 3. Then GΣ = {η1 , η2 , η3 },
span{R(Σ)} = span{Lη1 }⊕span{Lη3 }, and span{Lη2 } = span{Lη1 }. Clearly,
span{Lη1 } and span{Lη3 } are irreducible, thus span{R(Σ)} is semisimple.
Likewise, for the cycle Σ = (ΣT1 , ΣT2 ), span{R(Σ)} = span{Lηi }, i = 1, 2,
hence span{R(Σ)} is simple.
In general, the vector space U = span{R(Σ)} of an arbitrary composite
cycle Σ may have subspaces which are not invariant or do not contain any
binary row vector of Σ, or both. By contrast, if U is semisimple, U can be
decomposed into irreducible subspaces corresponding to the loops of their
generators, but some of these subspaces may coincide. This coincidence is
still considered as a degeneracy (see Section 4.3), which we exclude in the
class of separable cycles introduced next.

20

Definition 7. Let Σ be a composite cycle with generator GΣ , i.e. |GΣ | ≥ 2.
We call Σ separable, if span{R(Σ)} is semisimple and span{Lη } =
6 span{Lη0 }
0
0
for any η, η ∈ Gη with η 6= η . If Σ is not separable, Σ is said to be
inseparable.
Note that the hypotheses for a cycle Σ to be separable require that U =
span{R(Σ)} is invariant under P, i.e. separable cycles are a priori admissible.
Theorem 3. (Separability Condition for Composite Cycles) Let Σ be
a composite cycle with generator GΣ = {η1 , η2 , . . . , ηq }. Then Σ is separable,
if and only if
q
X
rank(ηi ).
(30)
rank(Σ) =
i=1

Proof. If Σ is separable, (30) follows directly from Proposition 3 and Definition 7.
Conversely, suppose (30) holds. Since
span{R(Σ)} = span{(

q
[

Lηi ) ∩ R(Σ)} ⊆ span{

i=1

q
[

Lηi },

i=1

(30) implies that span{Lηi ∩ R(Σ)} = span{Lηi } for each 1 ≤ i ≤ q,
span{Lηi } ∩ span{Lηj } = {0}, if i 6= j, and hence
span{R(Σ)} =

q
M

span{Lηi }.

i=1

It follows that each span{Lηi } is irreducible, thus Σ is separable according
to Definitions 6 and 7.
Example 3. Consider





Σ=





+
+
+
+
+
+
+

+
+
+
−
+
−
−

+
+
−
−
−
−
+

+
−
−
−
−
+
−
21

−
−
−
−
+
+
+

−
−
−
+
+
−
−

−
−
+
+
−
−
+

−
+
+
+
−
+
−






.





We have that GΣ = {η1 , η5 , η7 }, where ηj = rowj (Σ), 1 ≤ j ≤ 7. It is easy
to see that U1 = span{Lη1 }, U2 = span{Lη5 }, and U3 = span{Lη7 } intersect
trivially, hence
U = span(R(Σ)) = U1 ⊕ U2 ⊕ U3 ,
which implies that Σ is separable, and hence admissible.
4.3. Inseparable Composite Cycles
By Definition 7, inseparability of a composite cycle Σ happens in two
different cases. In the first case, the vector space U = span{R(Σ)} has
a reducible but indecomposable invariant subspace, which entirely contains
another invariant subspace as a subspace (see Example 1). This includes the
case where U is semisimple and span{Lη } = span{Lη0 } for two different generators η and η 0 (see Example 2). In the second case, the vector space U has
two or more indecomposable (reducible or not) invariant subspaces sharing
a nontrivial intersection as common proper subspaces. We now discuss the
admissibility of these two types of inseparable composite cycles.
Definition 8. Let GΣ = {η1 , η2 , . . . , ηq } be a generator of a cycle Σ. A
subset EGΣ = {1 , 2 , . . . , r }, r ≤ q, of GΣ is called an essential generator
of Σ, if EGΣ is minimal in the sense that
r
S
(a) span{R(Σ)} ⊆ span{ Li };
i=1

(b) for any i , j ∈ EGΣ with i 6= j, span(Li )∩span(Lj ) is a proper subspace
of both span(Li ) and span(Lj );
q
S
Lηj }, then ηi ∈ EGΣ .
(c) for every ηi ∈ GΣ , if ηi ∈
/ span{
j=1,j6=i

Note that an admissible cycle may have different sets of essential generators, i.e. EGΣ is in general not unique. Proposition 2 can be directly
rephrased in terms of essential generators.
Proposition 4. A cycle Σ is admissible, if for any essential generator EGΣ ,
L ⊂ span{R(Σ) ∩ L } for every  ∈ EGΣ . Conversely, if Σ is admissible
and EGΣ = {1 , . . . , r } is an essential generator of Σ, then
rank(Σ) ≤

r
X

rank(i ) ≤ |R(Σ)| ≤ N.

i=1

22

(31)

Remark 5. The condition (b) in Definition 8 includes three cases.
(a) For every i 6= j, span{Li } ∩ span{Lj } = {0}, and q = r. Composite
cycles in this case are separable.
(b) For every i 6= j, span{Li } ∩ span{Lj } = {0}, but q < r. Composite
cycles in this case are inseparable and degenerate. In this case U may be
q
L
semisimple or not, and has the complete decomposition U =
span{Li }
i=1

(see Proposition 3). Accordingly, we have that a degenerately inseparable
q
P
composite cycle Σ is admissible, if and only if rank(Σ) =
rank(i ). This
i=1

generalizes separable cycles and includes, for example, the case where for
some η ∈ R(Σ) also −η ∈ R(Σ), but Lη ∩ L−η = ∅ (see Example 2).
(c) For some i 6= j, span{Li } ∩ span{Lj } is a nontrivial proper subspace
of both invariant subspaces span{Li } and span{Lj }. Composite cycles in
this case are genuinely inseparable. This type of cycles is more complicated
than the other two. We next study the structure of this type of cycles, and
establish an admissibility condition.
Proposition 5. Let η and η̃ be two p-dimensional row vectors. If η ∈
span{Lη̃ }, then span{Lη } ⊆ span{Lη̃ }.
p
P
Proof. If η ∈ Lη̃ , we are done. Suppose η ∈ span{Lη̃ }, i.e., η =
αν η̃Pν ,
ν=1

 p
P
ν
t
αν η̃P Pt =
αν ∈ R, but η ∈
/ Lη̃ , then for every t ∈ {1, 2, . . . , p}, ηP =
p
P

ν=1
ν+t

(αν η̃P

), i.e., Lη ⊆ span{Lη̃ }, hence span{Lη } ⊆ span{Lη̃ }.

ν=1

Remark 6. Proposition 5 tells that if a row vector is in the vector space
spanned by the loop generated by another row vector of the same dimension,
then the vector space spanned by the loop generated by this row vector
is a subspace of the vector space spanned by the other one. Since for any
genuinely inseparable composite cycle, at least two indecomposable invariant
subspaces intersect nontrivially, it is natural to ask:
(a) Does there exist a row vector such that this nontrivial intersection is
spanned by the loop generated by it?
(b) If this row vector exists, can it be {−1, 1}-valued?
As we will see below in Proposition 6, the answer to the first question is
affirmative, however, it remains unclear whether there always exists a binary
23

row vector such that the loop generated by it spans the nontrivial intersection
of two indecomposable invariant subspaces. The approach we will use in the
proof of Proposition 6 only guarantees the existence of a genuine row vector,
which may or may not be binary.
Let V be defined as in Theorem 1, i.e. V = (v (0) , v (1) , . . . , v (p−1) ), where
v (k) = (1, ρk , ρ2k , . . . , ρ(p−1)k )T and ρ = e2πi/p .
Definition 9. A row vector η (not necessarily binary) is said to annihilate
the column v (k) of V , if ηv (k) = 0, i.e. the two vectors are orthogonal.
Note that, since v (k) is an eigenvector of P and all eigenvalues of P are
nonzero, η annihilates v (k) if and only if ηPν annihilates v (k) for every ν ∈ Z.
We need the following fact about the eigenvectors and eigenvalues of circulant
matrices, see, e.g., Lancaster & Tismenetsky (1985).
Lemma 1. Let η = (η 1 , . . . , η p ) be an arbitrary real and nonzero row vector,
and let Ση be the p × p-matrix defined by rowj (Ση ) = η(PT )(j−1) for 1 ≤
j ≤ p. Then V ∗ Ση = Λη V ∗ , where Λη = diag(λη,1 , . . . , λη,p ) with λη,k =
p
P
η j ρ(j−1)(k−1) .
j=1

Extending Definition 2 to non-binary real row vectors and noting that
R(Ση ) = Lη , an immediate consequence of Lemma 1 is the following:
Corollary 1. Assume that ηv (j) 6= 0 if and only if j ∈ {k1 , . . . , ks } ⊂ Zp ,
where Zp = {0, 1, 2, . . . , p − 1}. Then {v (k1 )∗ , . . . , v (ks )∗ } is a (complex) basis
for span{Lη }.
Proposition 6. Let Σ be a cycle with essential generator EGΣ = {1 , . . . , r }.
Assume that for some i 6= j the indecomposable subspaces Ui = span(Li ) and
Uj = span(Lj ) intersect nontrivially, and Ui ∩ Uj is a proper subspace of both
Ui and Uj . Then there exists a row vector η such that Ui ∩ Uj = span{Lη }.
Proof. Assume that i v (k) 6= 0 and j v (k) 6= 0 if and only if k ∈ Ki ⊂ Zp and
k ∈ Kj ⊂ Zp , respectively. Assume further that K ≡ Ki ∩ Kj = {k1 , . . . , ks }.
According to Corollary 1, {v (k1 )∗ , . . . , v (ks )∗ } is a basis for Ui ∩ Uj . Let pi (x)
and pj (x), x ∈ C, be the polynomials pi (x) = i x, pj (x) = j x, where
x = (1, x, x2 , . . . , xp−1 )T . Since the row vectors defined by the coefficients of
pi (x) and pj (x) annihilate exactly the v (k) with k ∈ Zp \Ki and k ∈ Zp \Kj ,
respectively, pi (x) and pj (x) contain the minimal polynomials of ρk for every
k ∈ Zp \Ki and k ∈ Zp \Kj , respectively, as factors. Multiplying these factors
yields a polynomial pij (x) of degree ≤ p − 1 with pij (ρk ) = 0 for every
24

k ∈ Zp \K and pij (ρk ) 6= 0 for every k ∈ K. Set p0 (x) = pij (x) if the degree
of pij (x) is p − 1. If the degree of pij (x) is < p − 1, set p0 (x) = pij (x)p̃ij (x),
where p̃ij (x) is any polynomial such that p̃ij (ρk ) 6= 0 for every k ∈ K and the
degree of p0 (x) is p − 1. Let η be the row vector of coefficients of p0 (x). Then
η and ηPν for any ν ∈ Z annihilate every v (k) for k ∈ Zp \K, and ηv (k) 6= 0
for every k ∈ K, hence span{Lη } = span{v (k1 )∗ , . . . , v (ks )∗ } = Ui ∩ Uj .
Example 4. In this example, we demonstrate how to find a row vector as
claimed in Proposition 6 with the method described in the proof. Consider
the composite cycle with N = 10 and p = 18 defined by Σ = (ΣT1 , ΣT2 )T ,
where
Σ1 = (T1 , (1 P)T , . . . , (1 P6 )T )T , Σ2 = (T2 , (2 P)T , (1 P2 )T )T ,
and
1 = ( + + + + + + + − + − − − − − − − + − ),
2 = ( + + + − − − + + + − − − + + + − − − ).
This is a genuinely inseparable composite cycle with GΣ = EGΣ = {1 , 2 }.
The polynomials p1 (x) and p2 (x) can be factorized as follows,
p1 (x) = (1 − x)(1 + x + x2 )(1 − x + x2 )(1 + x3 + x6 )(1 + 2x + 2x2 + x3 + x6 ),
p2 (x) = (1 − x)(1 + x + x2 )(1 − x3 + x6 )(1 + x3 + x6 )(1 + x − x2 ).
The factors 1 − x, 1 + x + x2 , 1 + x3 + x6 , 1 − x + x2 and 1 − x3 + x6 are
cyclotomic factors (see e.g. Dummit & Foote (2004)), and the sum of their
degrees happens to be 17. Multiplying them out gives
17
X
p0 (x) =
(−1)j xj ,
j=0

thus the row vector η constructed in the proof of Proposition 6 is obtained
as the binary vector with alternating signs, η = (+, −, +, −, . . . , +, −), and
span{Lη } = span{η}. One can easily verify that span{η} = span{L1 } ∩
span{L2 }.
Based on their structural features and using a simple inclusion-exclusion
argument, an admissibility condition for inseparable composite cycles can be
formulated as follows.
25

Theorem 4. (Admissibility Condition for Inseparable Composite
Cycles) Let Σ be a cycle with essential generator EGΣ = {1 , . . . , r }. Then
Σ is admissible if and only if
rank(Σ) =

r
P

rank(i ) −

i=1

+

r
P

dim(span{Li } ∩ span{Lj })

i,j;i6=j
r
P

dim(span{Li } ∩ span{Lj } ∩ span{Lk })

(32)

i,j,k;i6=j6=k

− · · · ± dim(

r
T

span{Li }).

i=1

Remark 7. The admissibility condition (32) is valid for any cycle, and the
conditions (30) and (28) for separability and admissibility of simple cycles,
respectively, can be thought of as special cases thereof.
Example 5. Let Σ be the cycle from Example 4. One can easily verify that
rank(1 ) = 7 and rank(2 ) = 3. Since dim(span{L1 } ∩ span{L2 }) = 1, this
cycle is admissible.
5. Network Topology
To simplify the discussion, we exclude in this section multiple appearances
of a binary row vector in a cycle, that is, we consider only cycles Σ with
|R(Σ)| = N .
The classification of cycles Σ in Section 4 was based on the decomposition
of R(Σ) into subsets of rows associated with disjoint loops. It is, therefore,
natural to identify the neurons corresponding to the same loop with a cluster.
However, if a cycle has fewer essential generators than generators, the row
vectors of a non-essential generator must be combined with one or more
essential generators and, moreover, there may be several choices for essential
generators. We therefore make the simplifying assumption that all generators
are essential generators. For admissible cycles Σ this means that for any two
distinct generators η1 , η2 , the intersection of their spaces span{Lηj ∩ R(Σ)},
j = 1, 2, is a proper subspace of both of them ({0} if the cycle is separable).
An immediate consequence of this assumption is that
rank(Σ) ≤

q
X

rank(ηj ) ≤ N,

j=1

26

(33)

if Σ is admissible and GΣ = {η1 , . . . , ηq }. The clusters are isolated if and
only if Σ is separable. If Σ is inseparable, some of the clusters are connected.
Regarding the connectivity within a cluster, linear dependences among
its row vectors will prevent any special structure. We call cycles for which
such dependences do not occur minimal.
Definition 10. An admissible cycle Σ with generator GΣ = {η1 , η2 , . . . , ηq }
is minimal, if EGΣ = GΣ and for every 1 ≤ i ≤ q,
|Lηi ∩ R(Σ)| = rank(ηi ).

(34)

Remark 8. If Σ is a minimal simple or separable composite cycle, then Σ is
of full row rank. If Σ is a minimal inseparable cycle, then the row vectors in
R(Σ)∩Lηi form a basis of span{Lηi } for every ηi ∈ GΣ . Thus for any minimal
cycle Σ, (33) holds and the inequalities become equalities if and only if Σ is
simple or separable. In this case, Σ has full row rank and Σ+ = ΣT (ΣΣT )−1 ,
which implies that J0 = ΣΣ+ = I, the N × N identity matrix.
For any two (N ×p)-cycles Σ and Σ0 with R(Σ) = R(Σ0 ), the cycle matrices
are related to each other by Σ0 = QΣ, where Q is an N × N permutation
matrix. If in addition Σ is admissible with connectivity matrix J̃, then Σ0
is also admissible and has connectivity matrix J̃0 = QJ̃Q−1 . Accordingly,
if u is the state of the network with connectivity matrix J̃, then u0 = Qu
is the network state corresponding to J̃0 , and solutions u(t) and u0 (t) of the
corresponding differential equations are just permutations of each other as
tanh(u0 ) = tanh(Q−1 u) = Q−1 tanh(u).
Without loss of generality, we therefore may assume that a minimal cycle
with generators η1 , . . . , ηq has the form
Σ = (ΣT1 , ΣT2 , . . . , ΣTq )T ,

(35)

where R(Σj ) ⊆ Lηj , 1 ≤ j ≤ q, and the vectors in Σj are sorted from top
to bottom as ηj , ηj1 , ηj2 , . . . , with ηji = sji ηj Pνji , sji = 1 if −ηj ∈
/ Lηj and
sji ∈ {−1, 1} if −ηj ∈ Lηj , and 0 < νji < νjk if i < k. We call this form the
standard form of a minimal cycle.
The minimality requirement does not suffice in general to induce a special
network topology within the clusters. We have to require in addition that
the powers in the Σj are consecutive.
Definition 11. A minimal cycle Σ in standard form is said to be a minimal
consecutive cycle, or briefly MC-cycle, if the powers of P in Σj above are
consecutive, that is, νji = i for all 1 ≤ i < rank(ηj ).
27

In order that Definition 11 is consistent with the minimality requirement,
the rows in Σj must be linearly independent. The next proposition shows
that this is indeed the case, where for simplicity we consider only the case
sji = 1.
Proposition 7. Let η 6= 0 be any p-dimensional row vector with rank(η) = k.
Then the vectors {η, ηP, ηP2 , . . . , ηPk−1 } are linearly independent.
Proof. Let s be the smallest positive integer such that {η, ηP, . . . , ηPs−1 } are
linearly independent. Then ηPs is a linear combination of {η, ηP, . . . , ηPs−1 },
ηPs =

s−1
X

αν ηPν .

(36)

ν=0

Right-multiplying this equation by P yields a representation of ηPs+1 as linear combination of {ηP, ηP2 , . . . , ηPs }, and replacing ηPs in this representation by (36) shows that ηPs+1 is also a linear combination of {η, ηP, . . . , ηPs−1 }.
By induction we find that, for any 0 ≤ ν < s − p, ηPs+ν is a linear combination of {η, ηP, . . . , ηPs−1 }, hence this set is a basis for Lη .
For simple MC-cycles there is only one cluster. In Subsection 5.1 we
discuss the possible connectivity structures in such networks in some detail,
including the possible values of N for a given p, and we also comment on the
network topology of simple minimal but non-consecutive cycles. Semisimple
MC-cycles consist of isolated clusters corresponding to the different loops
in the cycle. Each of these loops forms a simple MC-cycle, and we just
give an example in Subsection 5.2. Inseparable minimal (consecutive or nonconsecutive) cycles are more complicated and will be discussed in Subsection
5.3. In Subsection 5.4 we demonstrate the effects of fewer essential generators
than generators by two examples.
5.1. Simple MC-Cycles
5.1.1. Network Topology
According to Definition 11, a simple MC-cycle has the form
Σ = (η T , s1 (ηP)T , s2 (ηP2 )T , . . . , sN −1 (ηPN −1 )T )T ,

(37)

with rank(η) = N ≤ p and si ∈ {−1, 1}. Since the image of the last row
vector of Σ under P is a linear combination of the row vectors of Σ, ΣP has
28

the form ΣP = AΣ, where

0 s1
0
 0 0 s1 s2

 .. ..
..

.
A= . .
 0 0
0

 0 0
0
a1 a2 a3

...
...
...

0
0
..
.

0
0
..
.

. . . sN −3 sN −2
0
...
0
sN −2 sN −1
...
aN −1
aN






,




(38)

with a1 , . . . , aN ∈ R and a1 6= 0. Moreover, since Σ has full row rank,
Σ+ = ΣT (ΣΣT )−1 , which implies
J = ΣPΣ+ = A.

(39)

Equations (38) and (39) show that the network constructed from a simple
MC-cycle consists of a feed-forward chain from the N th neuron to the first
neuron, and feedback to the N th neuron from the subset of the neurons for
which ai 6= 0, which in any case includes the first neuron. If aj = 0 for
j > 1, then a1 = ±1, and the network topology is that of a ring, with either
excitatory (a1 = 1, J = PT if all sj = 1) or inhibitory connection (a1 = −1)
from neuron 1 to neuron N . Vectors of the form η = (σ, σ) or (σ, −σ) have
rank(η) ≤ p/2, and if rank(η) = p/2 = N we have either of these two types
of ring structures (see Subsection 5.1.3.).
Example 6. In Figure 3, A and B, we illustrate the topology of the networks
constructed from the following two simple MC-cycles,


+ + + + + + + − − − − − − −
 + + + + + + − − − − − − − + 


 + + + + + − − − − − − − + + 



Σ=
 + + + + − − − − − − − + + + ,
 + + + − − − − − − − + + + + 


 + + − − − − − − − + + + + + 
+ − − − − − − − + + + + + +
and




Σ̃ = 



+
+
−
+
−

+
−
+
−
−

−
+
−
−
+
29

+
−
−
+
+

−
−
+
+
−

−
+
+
−
+




,



respectively. The cycle Σ has a “repeating block structure”, Σ = [B, −B],
where B is the block consisting of the first 7 columns of Σ (N = p/2 = 7).
This causes the image of the last row to be the negative copy of the first row,
i.e. η7 P = −η1 , where ηi = rowi (Σ). It follows that a1 = −1 and ai = 0 for
i > 1, thus the first neuron only sends an inhibitory feedback to the seventh
neuron (Figure 3A). Similarly, for the cycle Σ̃, N = p − 1 = 5, and in this
case the image of the last row is a linear combination of all other row vectors,
η̃5 P = −η̃1 − η̃2 − η̃3 − η̃4 − η̃5 , where η̃i = rowi (Σ̃). Accordingly for this cycle
ai = −1 for every i, i.e. every neuron sends inhibitory feedback to the fifth
neuron in the network (Figure 3B).
The two examples above demonstrate that the value of N = rank(η) plays
an important role for the network topology of simple MC-cycles. We discuss
possible values of N for given cycle-lengths p in the next paragraph.
For minimal but non-consecutive cycles with N < p − 1 we can have
“gaps” in the standard form which lead to feedforward chains interrupted
by neurons with higher connectivities. The next example demonstrates this
possibility.
Example 7. Consider η = (+, +, +, +, +, +, −, −, −) (p = 9), and
Σ = (η T , (ηP)T , (ηP2 )T , (ηP4 )T , (ηP5 )T , (ηP6 )T , (ηP8 )T )T .
This cycle is minimal as rank(η) = rank(Σ) = 7, but not consecutive. The
gaps are between the third and fourth rows, and the sixth and seventh rows.
Since the seventh and first rows are consecutive, there are no other gaps.
The connectivity matrix is


0
1 0 0 0 0 0
 0
0 1 0 0 0 0 


 −1 0 1 0 1 −1 1 


0 0 0 1 0 0 
J=
 0
,
 0
0 0 0 0 1 0 


 0 −1 1 −1 1 0 1 
1
0 0 0 0 0 0
and shows that we still have the forward chain 3 → 2 → 1 → 7 → 6 → 5 → 4,
but neurons 3 and 6 receive multiple inputs. The network topology is shown
in Figure 3C.

30

5.1.2. N -p relations
Definition 12. Let Np : Xp → Ω be the function defined by Np (η) = n if η
annihilates (p − n) columns of V , where V is defined as in Theorem 1, Xp is
the set of binary row vectors of length p, and Ω = {1, 2, . . . , p − 1}.
Remark 9. It is a direct consequence of Theorem 1 that Np (η) = rank(η).
Therefore, for a given value of p, the image-set Np (Xp ) contains all possible
values of N for which there exists η ∈ Xp such that (37) defines a simple
MC-cycle. Furthermore, in Section 4.3 we have associated with η ∈ Xp
the polynomial pη (x) = η(1, x, . . . , xp−1 )T , where x is a complex variable.
Since pη (ρk ) = ηv (k) , ηv (k) = 0 (i.e. η annihilates v (k) ) if and only if pη (x)
has a factor which is a multiple of the minimal polynomial of ρk . Thus
Np (η) = rank(η) is intimately related to the factorization of pη (x).
There appears to be no general characterization of or formula for Np (η).
Even for row vectors with repeating block structure such as η = (σ, −σ)
or (σ, −σ, σ) (σ ∈ Xp/2 or Xp/3 ), the factorization of pη (x) does not reveal a
formalizable pattern. We therefore just list the sets Np (Xp ) in Table 1 for 1 ≤
p ≤ 20. Note that Nq (Xq ) ⊂ Np (Xp ) if q divides p, since rank(η) = rank(σ) if
η = (σ, σ, . . . , σ) (p/q repetitions) and σ ∈ Xq . We therefore include in Table
1 only those values N ∈ Np (Xp ), for which there exists a row vector η ∈ Xp
with N = rank(η), and η is NOT a repetition of some shorter vector σ. To
illustrate how Table 1 was obtained, we compute Np (η) for a row vector with
p = 6 in Example 8.
Remark 10. Vectors η of the form η = (σ, σ, . . . ) ∈ Xp with σ ∈ Xq have
minimal period ≤ q under cyclic permutations. The number of binary vectors
of minimal period p is found by subtracting the number of all vectors with
smaller minimal period from 2p . An inclusion/exclusion argument shows that
this number is given by
s
X
Mp = 2 −
(−1)k−1

X

p

k=1

2p/(pi1 pi2 ···pik ) ,

1≤i1 <···<ik ≤s

if p1 , p2 , . . . , ps are the distinct prime numbers occurring in the prime factorization of p (Mp = 2p − 2 if p is prime). Accordingly, the number of maximal
loops, i.e. loops with |Lη | = p, is Mp /p.
Example 8. Let η = (+, +, −, −, −, +). This vector has a repeating block
structure, η = (σ, −σ), where σ = (+, +, −). For p = 6 the matrix V is given
31

Table 1: Values of N ∈ Np (Xp ) attained by some η ∈ Xp that is NOT of the form
(σ, σ, . . . , σ) with σ ∈ Xq , q < p, for p ≤ 20.

p
N
1
1
2
1
3
3
4
2,4
5
5
6
3,5,6
7
7
8 4,6,7,8
9
7,9
10 5,9,10

p
N
11
11
12
6,7,8,9,10,11,12
13
13
14
7,13,14
15
11,13,15
16
8,10,11,12,13,14,15,16
17
17
18 7,9,11,12,13,14,15,16,17,18
19
19
20 10,12,13,14,15,16,17,18,19,20

by




(0) (1)
(5)
V = (v , v , . . . , v ) = 





1
1 1
1 1
1
1
ρ ρ2 −1 ρ4 ρ5 

1 ρ2 ρ4
1 ρ2 ρ4 
,
1 −1 1 −1 1 −1 

1 ρ4 ρ2
1 ρ4 ρ2 
1 ρ5 ρ4 −1 ρ2
ρ

where ρ = e2πi/6 . The polynomial pη (x) has the following factorization,
pη (x) = 1 + x − x2 − x3 − x4 + x5
= (1 − x3 )(1 + x − x2 )
= (1 − x)(1 + x + x2 )(1 + x − x2 ).
Since Φ1 (x) = x − 1 and Φ3 (x) = x2 + x + 1 are the first and the third
cyclotomic polynomials, and ρ0 = 1 is the primitive first root of unity and
ρ2 and ρ4 are the primitive third roots of unity, it follows that η annihilates
v (0) , v (2) and v (4) . Therefore, N6 (η) = 6 − 3 = 3.
Some of the N -values in Np (Xp ) in Table 1 can be explained directly,
without factorizing pη (x). We summarize three simple but important facts.
Proposition 8. (a) {1, p} ⊂ Np (Xp ) for any p > 2.
(b) If p > 2 is prime, then Np (Xp ) = {1, p}.
(c) p − 1 ∈ Np (Xp ) if p is even and p > 4.
32

Proof. Since rank(+, +, . . . , +) = 1, it follows that 1 ∈ Np (Xp ) for any p. To
show that p ∈ Np (Xp ) for p > 2, consider η = (−, +, +, . . . , +) and let Ση be
the p × p-matrix defined by rowj (Ση ) = η(PT )j−1 , 1 ≤ j ≤ p. By induction,
one shows that det(Ση ) = (−2)p−1 (p − 2) which completes the proof of (a).
Statement (b) is an immediate consequence of the fact that Φp (x) =
p
P
xj−1 is the minimal polynomial of ρk , 0 < k < p, if p is prime and is
j=1

irreducible over Q, hence if η 6= ±(+, +, . . . , +), Φp (x) and pη (x) cannot
contain a common factor.
To show (c), let σ = (+, −, +, −, . . . , +, −) ∈ Xp−2 and set η = (σ, −, +).
By performing elementary row operations on the matrix Ση with rows rowi (Ση )
= ηPi−1 , 1 ≤ i ≤ p − 1, it can be shown that Ση has full rank. The details
are straightforward but tedious to write down explicitly and will be omitted.
Remark 11. (a) If p is prime, then rank(η) = p for any η 6= ±(+, +, . . . , +).
For non-prime values of p one also can construct several different vectors
with rank(η) = p. For example, if p is odd, then rank(η) = p if η =
(+, −, +, −, . . . , +, −, +), which is easily shown using elementary
row opP i
erations. A generalization is provided by vectors η with
η = 1. All our
i

case studies indicate that these vectors have rank(η) = p as well.
(b) For even p > 4, the vector constructed in the proof of Proposition
8(c) is just one example
P iof a vector with rank(η) = p − 1. In general, if
1
p
η = (η , . . . , η ) and
η = 0, then η is orthogonal to (+, +, . . . , +), and
i

rank(η) ≤ p − 1. Case studies indicate that such a vector has maximal rank
p − 1 if it does not have a “repeating block structure”.
5.1.3. Simple anti-symmetric cycles
The characteristics of the cycles considered by Gencic et al. (1990) are
that the cycle length p is even and the second p/2 columns of the cycle matrix
are the negatives of the first p/2 columns in the same order. We call such
cycles anti-symmetric. Here we discuss the possible values of the rank of the
cycle matrix if these cycles are simple and admissible.
Proposition 9. Assume p is even, p = 2n, and η = (σ, −σ) with σ =
(σ 1 , . . . , σ n ) ∈ Xn . Then we have the following possibilities for rank(η).

33

Figure 3: Topology of networks constructed, respectively, by a simple MC-cycle with
N = p/2 = 7 (A, Example 6), a simple MC-cycle with N = p − 1 = 5 (B, Example
6), a minimal simple but non-consecutive cycle with N = p − 2 = 7 (C, Example 7),
a separable MC-cycle (D, Example 10) and a minimal genuinely inseparable composite
cycle (E, Example 11). In panels A-D, excitatory (inhibitory) synaptic connections are
labeled with red (blue) lines with arrowhead indicating the direction of the connections.
In panel E, in order to highlight the clusters in the network, connections within the same
clusters are labeled with black lines, and connections between neurons in different clusters
are labeled with dark red lines. Directions and polarities of the connections are not shown
in E. For all of the 5 networks illustrated in this figure, self-connectivities are not included.

34

(a) 1 ≤ rank(η) ≤ n. Moreover, d ≡ n − rank(η) is even, and if d ≥ 2 the
σ j satisfy d linearly independent homogeneous linear equations with integer
coefficients.
(b) If p = 2k , k ≥ 2, then rank(η) = n.
(c) If p = 2n with n > 2 prime and σ 6= ±(+, −, +, . . . , +, −, +), then
rank(η) = n.
Proof. (a) Let η = (σ, −σ), σ ∈ Xn , and define the p × p-matrix Σ by
rowj (Σ) = η(PT )j−1 , 1 ≤ j ≤ p. This matrix is a circulant matrix and
contains all rows of Lη , hence rank(η) = rank(Σ). According to the properties
of circulant matrices, the eigenvalues of Σ are of the form
λ=

p
X
i=1

i i−1

ηρ

=

n
X

(σ i − σ i ρn )ρi−1 ,

(40)

i=1

where ρ is any pth root of unity. Thus rank(η) coincides with the number of
distinct pth roots of unity for which the right-hand side of (40) is nonzero.
Since ηPn = −η, it follows that rank(η) ≤ n, and clearly rank(η) ≥ 1, which
proves the first statement of (a). To complete the proof of (a), we note that
the 2n distinct roots of x2n = 1 (x ∈ C) comprise n roots with xn = 1 and
n roots with xn = −1. Thus d = n − rank(η) coincides with the number of
distinct roots of xn = −1 for which
n
X
pσ (x) =
σ i xi−1 = 0.
(41)
i=1

If n is odd, pσ (−1) 6= 0, and if n is even, (−1)n = 1, thus all roots in question
have nonzero imaginary parts, which implies that d is even. If d ≥ 2, pσ (x) is
divisible by a cyclotomic polynomials Φm (x), where m divides n but not 2n.
The degree of Φm (x) is given by Euler’s totient function, ϕ(m), and is even.
The condition that pσ (x) factors through Φm (x) then leads to ϕ(m) linearly
independent homogeneous equations that must be satisfied by the σ i , and
since Φm (x) has integer coefficients, the coefficients of these equations can be
chosen as integers as well. If pσ (x) contains several cyclotomic polynomials
Φmj (x), 1 ≤ j ≤ r, as factors, the number of linear equations satisfied by σ
is ϕ(m1 ) + · · · + ϕ(mr ), and all these relations are linearly independent as
the cyclotomic polynomials are distinct and irreducible over the rationals.
(b) If p = 2k , k ≥ 2, the only factor that divides p but not n = 2k−1 is p.
The cyclotomic polynomial of p is Φp (x) = 1 + xn and has degree n, that is,
Φp (x) cannot be a factor of pσ (x) which has degree n − 1.
35

(c) Assume now that n > 2 is prime. In this case, Φ2n (x) = Φn (−x) is the
only cyclotomic polynomial in question and is given by Φn (−x) = 1−x+x2 −
x3 + · · · + xn . Thus, if σ is not of the form σ = ±(+, −, +, −, . . . , +, −, +),
Φn (−x) does not factor through pσ (x).
Since for η = (σ, −σ) a “rank deficiency” (rank(η) < n) occurs only
if σ satisfies a system of linear equations, the number of σ’s for which
rank(η) = n is considerably larger than the number of σ’s for which η
has a rank-deficiency. Thus “generically” we expect that vectors of the
form (σ, −σ) have full rank n. The vector σ = (+, −, +, −, . . . , +, −, +)
is, of course, a very special case as (σ, −σ) has the repeating block structure
(+, −, +, −, . . . , +, −) which has minimal rank 1. We illustrate the occurrence of rank deficiencies by an example.
Example 9. Let p = 18 = 2 · 32 , i.e. n = 9. The cyclotomic polynomials
that can give rise to a rank deficiency are here Φ6 (x) = 1 − x + x2 and
Φ18 (x) = 1 − x3 + x6 . The condition that pσ (x) = σ 1 + σ 2 x + · · · + σ 9 x8
factors through Φ6 (x) leads to the equations
σ 1 − σ 3 − σ 4 + σ 6 + σ 7 − σ 9 = 0,
σ 2 + σ 3 − σ 5 − σ 6 + σ 8 + σ 9 = 0.
The only binary vector satisfying these conditions (up to cyclic permutations)
are ±σ (1) , ±σ (2) and ±σ (3) , where
σ (1) = (+, +, +, +, +, +, +, −, +),
σ (2) = (+, +, +, −, +, +, −, −, +),
σ (3) = (+, +, −, +, +, −, +, −, +).
Since Φ6 (x) has a single pair of complex conjugate roots, rank(σ (ν) , −σ (ν) ) =
9 − 2 = 7, ν = 1, 2, 3. Similarly, in order that Φ18 (x) factors through pσ (x),
the conditions σ j + σ j+3 = 0 for 1 ≤ j ≤ 6 must be satisfied, leading
to rank(σ, −σ) = 3. All vectors with block structure σ = (σ̃, −σ̃, σ̃) with
σ̃ ∈ X3 have this property, and lead to η = (σ̂, σ̂, σ̂) with σ̂ = (σ̃, −σ̃), i.e.
rank(η) = rank(σ̂). This includes σ̃ = (+, +, +) with rank(σ̂) = 3, and
σ̃ = (+, −, +) with rank(σ̂) = 1. In the latter case, both Φ6 (x) and Φ18 (x)
are factors of pσ (x).
The rank of generic vectors (without rank deficiency) of the form (σ, σ)
or (σ, −σ) is equal to the length of σ. The converse question is under which
circumstances a vector η ∈ Xp with p even and rank(η) = p/2 has this form.
We state two simple sufficient conditions for this property.
36

Proposition 10. Assume p = 2n, η ∈ Xp , and rank(η) = n. If p = 2k ,
k ≥ 2, or n > 2 is prime, then η is either of the form (σ, σ) or (σ, −σ) for
some σ ∈ Xn .
Proof. Let η = (σ, σ̂) with σ, σ̂ ∈ Xn . We consider again the matrix Σ
defined in the proof of Proposition 9 with eigenvalues
λ=

n
X

(σ i + ρn σ̂ i )ρi−1 ,

i=1

where ρ is a pth root of unity, p = 2n. Assuming that rank(η) = n, there
exist precisely n distinct roots ρ of x2n = 1 for which λ = 0. We decompose
these roots again into roots satisfying xn = 1 and xn = −1, respectively, and
set accordingly
n
X
λ± (x) =
(σ i ± σ̂ i )xi−1 .
i=1

(a) Assume that p = 2k (n = 2k−1 ) for k ≥ 2. If there exists a root ρ of
xn = −1 for which λ = 0, λ(x) must contain the cyclotomic polynomial
Φ2n (x) = 1 + xn as a factor, which is only possible if σ i − σ̂ i = 0 for all
i, because λ(x) has at most degree n − 1. Thus η = (σ, σ) in this case.
Conversely, assume that all roots ρ for which λ = 0 are roots of xn = 1. Then
λ+ (x) must contain all cyclotomic polynomials Φν (x) for ν = 1, 2, . . . , 2k−1
as factors. Since the product of these polynomials is 1 − xn , this cannot hold
unless σ i + σ̂ i = 0 for all i, thus η = (σ, −σ) in this case.
(b) The case p = 2n with n > 1 prime is treated similarly. Here the cyclotomic polynomials which factor through xn − 1 are 1 − x and Φn (x) =
1 + x + · · · + xn−1 , and the cyclotomic polynomials which factor through
1 + xn are 1 + x and Φn (−x). Since n > 1, either Φn (x) is a factor of
λ+ (x) or Φn (−x) is a factor of λ− (x), which implies that either σ̂ = σ or
σ̂ = −σ.
An extension of Proposition 10 to more general values of p appears highly
nontrivial, because a multitude of cyclotomic polynomials have to be considered if the prime factorization of n is more complicated. We have examined
all vectors η with rank(η) = p/2 for p ≤ 20 and found that all these vectors
have the form (σ, σ) or (σ, −σ). Other vectors with rank(η) = p/2 may exist
for larger values of p, but if so we expect the number of these vectors to be
much smaller than the number of (σ, σ)- or (σ, −σ)-vectors of full rank.
37

5.2. Separable MC-Cycles
For separable MC-cycles with generators GΣ = {η1 , η2 , . . . , ηq }, the spaces
span{Lηj } and span{Lηk } intersect trivially if j 6= k. If Σ is in standard form,
this implies immediately that J has a block structure, J = diag(J1 , . . . , Jr ),
where Jk is an Nk × Nk -matrix of the form (38) with Nk = rank(ηk ). Accordingly, a network constructed from a separable MC-cycle is decomposed
into r disconnected clusters and for each cluster the connectivity matrix has
the form corresponding to a simple MC-cycle.
Example 10. Consider the

+
 +

 +

Σ=
 +
 +

 +
+

7 × 8-cycle
+
+
+
−
+
−
−

+
+
−
−
−
−
+

+
−
−
−
−
+
−

−
−
−
−
+
+
+

−
−
−
+
+
−
−

−
−
+
+
−
−
+

−
+
+
+
−
+
−






.





This cycle has the generators η1 , η5 , η7 (ηj = rowj (Σ)) and is separable and
in standard form. Moreover, η4 P = −η1 , η6 P = −η5 , and η7 P = −η7 . Thus
the network is decomposed into three clusters consisting of neurons 1, 2, 3,
4, neurons 5, 6, and neuron 7, with cycle-connectivity matrices


0 1 0 0


 0 0 1 0 
0
1


,
 0 0 0 1 ,
−1 0
−1 0 0 0
and −1, respectively. The topology of this network is illustrated in Figure
3D. We note, however, that the cluster consisting of neuron 7 cannot show
oscillations without delay, since a 1D dynamical system does not have limit
cycles. By contrast, with delay included, we can find oscillations already for
N = 1 for appropriate parameter values.
General separable cycles still can be decomposed into isolated clusters
as span{R(Σ)} is semisimple, however, the network topology in each cluster
maybe more complicated (see Subsection 5.4). The issue with separable
cycles is that, even if the subcycles corresponding to the different clusters are
retrieved, these oscillations are in general not synchronized. We comment on
this issue further in Section 6.
38

5.3. Minimal Inseparable Cycles
For minimal inseparable cycles Σ with generators GΣ = {η1 , η2 , . . . , ηq },
at least two subspaces span{Lηj ∩ R(Σ)} and span{Lηk ∩ R(Σ)} (j 6= k) have
a nontrivial intersection. Accordingly, Σ does not have full row-rank,
rank(Σ) <

q
X

rank(ηi ) = N,

i=1

which implies in particular that J0 6= I. It is still possible to partition the
network into clusters, but some clusters may be connected and the network
topology within the cluster corresponding to the loop Lηj will in general
not coincide with the network topology predicted by the submatrix Σj of
the corresponding simple cycle. Thus the consecutiveness requirement does
not have an effect, whereas the minimality requirement takes care that the
sub-matrices in J0 and J defining the connectivities within the clusters are
non-singular. The following example illustrates these features.
Example 11. Consider the 10 × 12-cycle Σ = (ΣT1 , ΣT2 , ΣT3 )T , where
ΣT1 = (η1T , (η1 P)T , (η1 P2 )T , (η1 P3 )T )T ,
ΣTj = (ηjT , (ηj P)T , (ηj P2 )T )T , j = 2, 3,
with

η1 = ( + + + − + + + − + + + − ),
η2 = ( − + + + − − − + + + − − ),
η3 = ( + − − + − − + − − + − − ).

This is a minimal inseparable admissible cycle with generator GΣ = {η1 , η2 , η3 }.
The connectivity matrix J is given by


0
7
0 −1
1 −1
1 −1 −1 −1
 −1
0
7
0 −1
1 −1 −1 −1 −1 


 0 −1

0
7
1
−1
1
−1
−1
−1


 7
0 −1
0 −1
1 −1 −1 −1 −1 



1
1
−1
1
−1
2
6
2
0
0
0
,
J= 

−1
1
−1
1
−2
2
6
0
0
0
8


 1 −1
1 −1
6 −2
2
0
0
0 


 −1 −1 −1 −1

0
0
0
−2
6
−2


 −1 −1 −1 −1
0
0
0 −2 −2
6 
−1 −1 −1 −1
0
0
0
6 −2 −2
39

and J0 has the same block structure as J (with self-feedbacks of all neurons). From the form of J (and J0 ) we infer that the cluster corresponding
to η1 is connected to the clusters corresponding to η2 and η3 , while the latter
two clusters are not directly connected. This connectivity structure is due
to the fact that span{Lη1 } intersects span{Lη2 } and span{Lη3 } in the onedimensional spaces spanned by (+, −, +, −, . . . , +, −) and (+, +, +, . . . , +),
respectively, whereas span{Lη2 } and span{Lη3 } intersect trivially. The network topology for this example is shown in Figure 3E. In general, two clusters
corresponding to two generators η, η 0 ∈ GΣ are connected, if there exists a
sequence η = η1 , η2 , . . . , ηs−1 , ηs = η 0 of generators such that span{Lηj } and
span{Lηj+1 } intersect nontrivially for 0 ≤ j < s.
5.4. Further Examples
The examples in this subsection serve to illustrate the possible effects of
fewer essential generators than generators. Consider a cycle Σ with EGΣ =
{1 , . . . , r }. If r < |GΣ |, the loop vectors of at least one generator are
contained in the span of the loop vectors of another essential generator.
Assuming |R(Σ)| = N , this implies
rank(Σ) ≤

r
X

rank(i ) < N,

i=1

and we encounter again a rank-deficiency that will destroy special structures
in the clusters corresponding to the essential generators.
Example 12. The 6 × 6-cycle

+
 +

 −
Σ=
 −

 +
+

+
−
−
+
−
−

−
−
+
−
+
+

−
+
−
+
+
−

+
−
+
+
−
+

−
+
+
−
−
−





,




has two generators, row1 (Σ) and row6 (Σ), but row6 (Σ) = row1 (Σ)+row3 (Σ)+
row5 (Σ), thus there is only one essential generator,  = row1 (Σ). Without the
sixth row, Σ would be a simple MC-cycle with ring-topology. The presence

40

of the sixth row destroys this structure, which is revealed in the following
forms of J0 and J,




3 0 −1 0 −1 1
0
4
0
0
0
0
 0 4
 −1
0 0
0 0 
0
3
0 −1
1 








1
1
−1
0
3
0
−1
1
0
0
0
4
0
0
, J = 
.
J0 = 
 −1


0
0
0
4
0
0
0
−1
0
3
1
4
4




 −1 0 −1 0
 −1 −4 −1 −4 −1 −3 
3 1 
1 0
1 0
1 3
−1
0 −1
0 −1 −3
Example 13. The cycle



1 −1
1
1 −1  ,
Σ =  −1
1
1
1
has three generators and one essential generator that can be chosen as the
first or second row. Since Σ is non-singular, Σ is admissible and J0 is the
identity matrix. A successfully retrieved cycle shows three consecutive phases
1, 2, and 3 during an oscillation. In phases 1 and 2, neuron 1 is “on” (+)
and in phase 3 it is “off” (−), while neuron 2 is “on” in phase 1 and “off” in
phases 2 and 3. Clearly, neuron 3 is “on” during all 3 phases. The matrix J
is given by


−1 1 1
J =  −1 0 0  ,
0 0 1
and shows that neurons 1 and 2 form an excitatory/inhibitory pair, whereas
neuron 3 acts excitatory on neuron 1. Without this third neuron the oscillations of neurons 1 and 2 as required by the first two rows of Σ could not
be implemented, since the submatrix of Σ consisting of these rows is not
admissible.
6. Discussion and Conclusion
In this paper we have studied the structural features of admissible cycles
and their relation to the topology of the corresponding networks. While our
main motivation was the storage of cycles in continuous-time Hopfield-type
networks, the results apply to other networks as well, including the discrete
networks considered by Personnaz et al. (1986) and Guyon et al. (1988) and
41

networks of spiking neurons exhibiting up-down states. In particular, we
have formulated and proved conditions on binary cyclic patterns that guarantee the existence of a network with connectivity satisfying the transition
conditions imposed by the cycle, independent of the specific dynamics of the
individual neurons.
We showed that if and only if the discrete Fourier transform Σ̂ = ΣV of
a cycle matrix Σ contains exactly r nonzero columns, where r = rank(Σ),
then a network can be constructed from Σ with the pseudoinverse learning
rule. Based on the structural analysis of the invariant subspaces of the row
space of Σ, the admissible cycles have been classified into simple cycles, and
separable and inseparable composite cycles. This classification was based
on the decomposition of the row space of Σ into subsets corresponding to
disjoint loops. The admissibility of a cycle implied that all vectors of a
loop are in the row space of Σ if Σ contains some of these loop vectors. If
no loop-space associated with Σ is a subspace of another loop-space (the
generators are essential generators), we have identified for each loop the
neurons associated with the loop vectors contained in Σ with a cluster. For
general admissible cycles the clusters are connected, and the connectivity of
the clusters depends on the intersections of their loop-spaces. Two clusters
are directly connected if their indecomposable invariant subspaces intersect
non-trivially. They are “indirectly” connected if they are part of a chain of
directly connected clusters.
If an admissible cycle is separable, the clusters are completely isolated.
In this case each cluster corresponds to a simple cycle associated with a
generator of Σ. If the simple cycle is minimal and consecutive, the cluster
has the form of a feedforward chain from the last neuron to the first neuron
with feedbacks to the last neuron from the other neurons. If in addition
the length of the cycle, p, is even and the rank of the generator is p/2, we
generically find a ring structure with excitatory or inhibitory connection from
the first neuron to the last neuron, but we cannot exclude that special loops
with these properties exist for which no ring-structure occurs. If the simple
cycle is minimal but non-consecutive, we find more than one feedforward
chains.
Regarding non-minimal simple as well as composite cycles, it would be
interesting to find equivalence relations similar to those of Golubitsky et al.
(2005), and Golubitsky & Stewart (2006), relating networks constructed from
non-minimal cycles to networks constructed from minimal cycles. For example, similar to the linear-threshold (LT) networks (Tang et al, 2006, 2010),
42

we may consider the Hopfield-type network (10) with delay in a different but
closely related form,

u̇ = −u + tanh β C0 J0 u + C1 Juτ ,
(42)
where β = βK λ and uτ = u(t − τ ). While (10) is invariant under arbitrary
permutations of the neurons, it can be shown that (42) is invariant under a
larger class of linear transformations that allows to define broad equivalence
relations among admissible cycles. In comparison to (10), the only disadvantage (42) may have is that it is less biologically plausible, because in biological
neural networks neurons usually are coupled with each other through chemical synapses, which means that the firing rates instead of the membrane
potentials of the presynaptic neurons change the membrane potential of the
postsynaptic neuron.
In networks constructed from composite cycles, the complete isolation of
the clusters of separable cycles means that each cluster has its own subcycle.
The issue is that we cannot expect the different subcycles to synchronize,
preventing the network to traverse the cycle states in the order prescribed
by the cycle matrix. In this case an additional synchronization mechanism
must be introduced to enforce synchrony. Such a mechanism can be in the
form of a small coupling among the clusters or through an external periodic
input acting as pacemaker.
The generation of cyclic patterns in animal nervous systems is associated with CPG networks, and the storage and retrieval of cyclic patterns
in such networks are fundamentally important. Recent experimental observations (e.g. Dickinson & Moulins, 1992; Meyrand et al., 1994; Jean, 2001)
suggested that CPGs may be highly flexible. As some animal movements,
such as swallowing, gastrointestinal motility etc., often require the coordination of several functional groups of muscles, different CPGs controlling these
muscles subsequently form during different phases of the movements. Such
CPG networks consist of pools of neurons that can function in several CPGs
involved in the organization of various motor behavior.
Recently, in order to account for the flexibility of memory representation
observed in neurophysiological experiments, Tang et al (2010) studied the
effect of saliency weights on the memory dynamics in LT neural networks.
They showed that the saliency distribution determines the retrieval process
of the stored patterns, and that a nonuniform saliency distribution can contribute to the disappearance of spurious states. Using our results on the
43

relation between the structural features of a cycle and the network topology,
a mechanism similar to the variable saliency factor introduced by Tang et
al (2010) into LT networks may be used to combine different CPGs in one
network, and to study how a sequence of several cycles determines a changing
network structure.
Acknowledgement
The authors would like to thank the anonymous reviewers for their valuable comments and suggestions, and Alexander Hulpke and Chuck Anderson
for helpful discussions. The first author was supported in part by a Summer Graduate Research Fellowship (2012) awarded by the Department of
Mathematics at Colorado State University.
Appendix A. Cyclotomic Polynomials
We summarize here the basic properties of the cyclotomic polynomials
used in Sections 3-5, for details see Dummit & Foote (2004). Q
The cyclotomic polynomial of order p is defined by Φp (x) = r (x − xr ),
x ∈ C, where the xr encompass all primitive p-th roots of unity, that is,
xpr = 1 and xnr 6= 1 if 1 ≤ n < p. The total number
primitive
Q ofmsuch
j
roots is given by Euler’s totient function, ϕ(p). If p = j pj with distinct
Q m −1
primes pj is the prime factorization of p, then ϕ(p) = j pj j (pj − 1). The
important property of the cyclotomic polynomial is that they have integer
coefficients and are irreducible over the rationals. Moreover, Φp (x) is the
minimal polynomial for each root xr , and the product of all Φd (x) for which
d is a factor of p and 1 ≤ d ≤ p is xp − 1. The only cyclotomic polynomials
of odd degree are Φ1 (x) = 1 − x and Φ2 (x) = 1 + x, all Φp (x) for p > 2 have
even degrees as their primitive roots are all complex. Some basic properties
of Φp (x) are:
p
X
Φp (x) =
xi−1 if p is prime,
i=1

Φ2p (x) = Φp (−x) if p is odd,
Φp (x) = Φq (xp/q ),

44

where q is the radical of p, i.e. the product of all distinct prime numbers
occurring in the prime factorization of p. The last property implies in particular Φp (x) = 1 + xn if p = 2n = 2k , k ≥ 1. The third cyclotomic polynomial
is Φ3 (x) = 1 + x + x2 and has the roots e±2πi/3 .
References
References
Amari, S.-I. (1977) Neural theory of association and concept-formation. Biol.
Cybern. 26(3), 175-185
Cossart, R., Aronov, D. & Yuste, R. (2003) Attractor dynamics of network
UP states in neocortex. Nature 423, 283-289
Dayan, P. & Abbott, L.F. (2001) Theoretical neuroscience - computational
and mathematical modeling of neural systems. The MIT Press: Cambridge,
Massachusetts
Dickinson, P.S. & Moulins, M. (1992) Interactions and combinations between
different networks in the stomatogastric nervous system. In: Dynamic biological networks: the stomatogastric nervous system Harris-Warrick, R.M.,
Marder, E., Selverston, A.I., and Moulins, M. (eds) Cambridge, MA: MIT,
139-160
Dummit, D.S. & Foote, R.M. (2004) Abstract Algebra (3rd ed.) John Willey
& Sons, Inc.: Hoboken, NJ
Gencic, T., Lappe, M., Dangelmayr, G. & Guettinger, W. (1990) Storing
cycles in analog neural networks. In Parallel Processing in Neural Systems
and Computers, Eckmiller, R., Hartmann, G. and Hauske, G. (eds.), North
Holland, 445-450
Golubitsky, M., Stewart, I., Buono, P.-L. & Collins, J.J. (1999) Symmetry in
locomotor central pattern generators and animal gaits. Nature 401, 693-695
Golubitsky, M., Stewart, I. & Török, A. (2005) Patterns of synchrony in
coupled cell networks with multiple arrows. SIAM J. Appl. Dynam. Sys.
4(1), 78-100

45

Golubitsky, M. & Stewart, I. (2006) Nonlinear dynamics of networks: the
groupoid formalism. Bull. Amer. Math. Soc., 43(3), 305-364
Grillner, S. (2003) The motor infrastructure: from ion channels to neuronal
networks. Nature Rev. Neurosci. 4, 573-586
Guyon, I., Personnaz, L., Nadal, J.P. & Dreyfus, G. (1988) Storage and
retrieval of complex sequences in neural networks. Phys. Rev. A, 38(12),
6365-6372
Hopfield, J.J. (1982) Neural networks and physical systems with emergent
collective computational abilities. Proc. Natl. Acad. Sci. USA 79, 25542558
Hopfield, J.J. (1984) Neurons with graded response have collective computational properties like those of two-state neurons. Proc. Natl. Acad. Sci.
USA 81, 3088-3092
Jean, A. (2001) Brain stem control of swallowing neuronal network and cellular mechanisms. Physiol. Rev. 81(2), 929-969
Kanter, I. & Sompolinsky, H. (1987) Associative recall of memory without
errors. Phys. Rev. A 35, 380-392
Kleinfeld, D. & Sompolinsky, H. (1988) Associative neural network model
for the generation of temporal patterns, theory and application to central
pattern generators. Biophys. J. 54, 1039-1051
Korn, H. & Faure, P. (2003) Is there chaos in the brain? II. Experimental
evidence and related models. Comptes Rendus Biologies 326(9), 787-840
Lancaster, P. & Tismenetsky, M. (1985) The theory of matrices. (2nd ed.)
Academic Press: San Diego
Little, W.A. (1974) The existence of persistent states in the brain. Math.
Biosci. 19, 101-120
López-Rodrı́guez, D., Mérida-Casermeiro, E. & Ortiz-de-Lazcano-Lobato,
J.M. (2005) Hopfield network as associative memory with multiple reference points. World Academy of Science, Engineering and Technology 7,
62-67
46

MacKay-Lyons, M. (2002) Central pattern generation of locomotion: a review of the evidence. Phys. Ther. 82, 69-83
Marder, E., Bucher, D., Schulz, D.J. & Taylor, A.L. (2005) Invertebrate
central pattern generation moves along. Curr. Biol. 15, R685-R699
Marinaro, M., Scarpetta, S. & Yoshioka, M. (2007) Learning of oscillatory
correlated patterns in a cortical network of a STDP-based learning rule.
Math. Biosci. 207, 322-335
McEliece, R.J., Posner, E.C., Rodemich, E.R. & Venkatesh, S.S. (1987) The
capacity of the Hopfield associative memory. IEEE Transactions on Information Theory IT-33(4), 461-482
Meyrand, P., Simmers, J., & Moulins, M. (1994) Dynamic construction of a
neural network from multiple pattern generators in the lobster stomatogastric nervous system. J. Neurosci. 14, 630-644
Miller, W. Jr. (1972) Symmetry groups and their applications. Academic
Press: New York
Parga, N. & Abbott, L.F. (2007) Network model of spontaneous activity
exhibiting synchronous transitions between up and down states. Front.
Neurosci. 1(1), 57-66
Personnaz, L., Guyon, I. & Dreyfus, G. (1986) Collective computational
properties of neural networks: new learning mechanisms. Physical Review
A, 34(5), 4217-4228
Rojas, R. (1996) Neural networks - a systematic introduction. SpringerVerlag: New York
Sanchez-Vives, M. & McCormick, D. (2000) Cellular and network mechanisms of rhythmic recurrent activity in neocortex. Nature Neurosci. 3,
1027-1034
Selverston, A.I.(2010) Invertebrate central pattern generator circuits. Phil.
Trans. R. Soc. B 365: 2329-2345
Šı́ma, J. & Orponen, P. (2003) Continuous-Time symmetric Hopfield nets
are computationally universal. Neural Computation 15: 693-733
47

Straub, V.A., Staras, K., Kemenes, G. & Benjamin, P.R. (2002) Endogenous and network properties of Lymnaea feeding central pattern generator
interneurons. J. Neurophysiol. 88, 1569-1583
Tang, H., Tan, K.C. & Teoh, E.J. (2006) Dynamics analysis and analog
associative memory of networks with LT neurons. IEEE Trans. Neural
Networks 17(2), 409-418
Tang, H., Li, H. & Yan, R. (2010) Memory dynamics in attractor networks
with saliency weights. Neural Computation 22, 1899-1926
Tapson, J. & Schaik, A. (2013) Learning the pseudoinverse solution to network weights. Neural Networks, http://dx.doi.org/10.1016/j.neunet.
2013.02.008
Wang, D.L. & Arbib, M.A. (1990) Complex temporal sequence learning based
on short-term memory. Proc. IEEE, 78, 1536-1543
Wang, D.L. (2003) Temporal pattern processing. In The Handbook of Brain
Theory and Neural Networks, 2nd Ed., Arbib M.A. (ed.), MIT Press, Cambridge MA, 1163-1167
Yuste, R. (2008) Circuit neuroscience: the road ahead. Front. Neurosci., 2,
6-9
Zifan, A., Gharibzadeh, S. & Moradi M.H. (2007) Could dynamic attractors
explain associative prosopagnosia? Medical Hypotheses 68, 1399-1405

48

