Dominique Perrin

Codes and automata in minimal sets

We explore several notions concerning codes and automata in a restricted set of words S. We define a notion of S-degree of an automaton and prove an inequality relating the cardinality of a prefix code included in a minimal set S and its S-degree.

Introduction

We have introduced in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF] the notion of tree set as a common generalization of Sturmian sets and of interval exchange sets. In this paper, we investigate several new directions concerning codes and automata in minimal sets.

Codes and automata in restricted sets of words have already been investigated several times. In particular, Restivo has investigated codes in sets of finite type [START_REF] Restivo | Codes and local constraints[END_REF] and Reutenauer has studied the more general notion of codes of paths in a graph [START_REF] Reutenauer | Ensembles libres de chemins dans un graphe[END_REF]. We have initiated in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] with several other authors, a systematic study of bifix codes in Sturmian sets, a subject already considered before in [START_REF] Carpi | Codes of central Sturmian words[END_REF]. The overall conclusion of this study is that very surprising phenomena appear in this context in relation with subgroups of finite index of the free group, allowing one to obtain positive bases of the subgroups contained in a given minimal set.

In this paper, we investigate several notions concerning codes and automata in relation with a factorial set S. This includes a definition of minimal S-rank of an automaton, which is equal to 1 if and only if the automaton is synchronized. We prove a result which allows to compute the minimal S-rank when S is minimal (Theorem 3.1). We also show that for a recurrent set S and a strongly connected automaton A, the set of elements of the transition monoid M of minimal S-rank is included in a D-class of M called its S-minimal D-class (Proposition 3.2). This regular D-class is unique when S is minimal and it is related with the results of [START_REF] Almeida | On the transition semigroups of centrally labeled Rauzy graphs[END_REF] and [START_REF] Almeida | Presentations of Schützenberger groups of minimal subshifts[END_REF] on the regular J -classes of free profinite semigroups.

We define the S-degree of a prefix code X included in S as the minimal Srank of the minimal automaton of X * . We show that the cardinality of a prefix code is bounded below by a linear function of its S-degree (Theorem 4.4).

Let X be a prefix code and let M be the transition monoid of the minimal automaton of X * . We associate to X a permutation group denoted G X (S) which is the structure group of the S-minimal D-class of M . We show that for any uniformly recurrent tree set S and any finite S-maximal bifix code X, the group G X (S) is equivalent to the representation of the free group on the cosets of the subgroup generated by X (Theorem 4.5).

Let A be a finite alphabet. We denote by A * the set of all words on A. We denote by ε or 1 the empty word. A set of words on the alphabet A and containing A is said to be factorial if it contains the factors of its elements. An internal factor of a word x is a word v such that x = uvw with u, w nonempty.

Neutral sets

Let S be a factorial set on the alphabet A. For w ∈ S, we denote

L S (w) = {a ∈ A | aw ∈ S}, R S (w) = {a ∈ A | wa ∈ S}, E S (w) = {(a, b) ∈ A × A | awb ∈ S}, and further ℓ S (w) = Card(L S (w)), r S (w) = Card(R S (w)), e S (w) = Card(E S (w)).
We omit the subscript S when it is clear from the context. A word w is rightextendable if r(w) > 0, left-extendable if ℓ(w) > 0 and biextendable if e(w) > 0. A factorial set S is called right-extendable (resp. left-extendable, resp. biextendable) if every word in S is right-extendable (resp. left-extendable, resp. biextendable).

A word

w is called right-special if r(w) ≥ 2. It is called left-special if ℓ(w) ≥ 2. It is called bispecial if it is both left-special and right-special. For w ∈ S, we denote m S (w) = e S (w) -ℓ S (w) -r S (w) + 1.
A word w is called neutral if m S (w) = 0. We say that a set S is neutral if it is factorial and every nonempty word w ∈ S is neutral. The characteristic of S is the integer χ(S) = 1 -m S (ε).

A neutral set of characteristic 1, simply called a neutral set, is such that all words (including the empty word) are neutral.

The following is a trivial example of a neutral set of characteristic 2.

Example 2.1. Let A = {a, b} and let S be the set of factors of (ab) * . Then S is neutral of characteristic 2. As a more interesting example, any Sturmian set is a neutral set [START_REF] Berthé | Acyclic, connected and tree sets[END_REF] (by a Sturmian set, we mean the set of factors of a strict episturmian word, see [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF]).

The following example is the classical example of a Sturmian set. The factor complexity of a factorial set S of words on an alphabet A is the sequence p n = Card(S ∩ A n ). The complexity of a Sturmian set is p n = n(Card(A) -1) + 1. The following result (see [START_REF] Dolce | Enumeration formulae in neutral sets[END_REF]) shows that a neutral set has linear complexity. Proposition 2.1 The factor complexity of a neutral set on k letters is given by p 0 = 1 and p n = n(k -χ(S)) + χ(S) for every n ≥ 1.

Example 2.3. The complexity of the set of Example 2.1 is p n = 2 for any n ≥ 1.

A set of words S = {ε} is recurrent if it is factorial and for any u, w ∈ S, there is a v ∈ S such that uvw ∈ S. An infinite factorial set is said to be minimal or uniformly recurrent if for any word u ∈ S there is an integer n ≥ 1 such that u is a factor of any word of S of length n. A uniformly recurrent set is recurrent.

Tree sets

Let S be a biextendable set of words. For w ∈ S, we consider the set E(w) as an undirected graph on the set of vertices which is the disjoint union of L(w) and R(w) with edges the pairs (a, b) ∈ E(w). This graph is called the extension graph of w. We sometimes denote 1 ⊗ L(w) and R(w) ⊗ 1 the copies of L(w) and R(w) used to define the set of vertices of E(w). We note that since E(w) has ℓ(w) + r(w) vertices and e(w) edges, the number 1 -m S (w) is the Euler characteristic of the graph E(w).

A biextendable set S is called a tree set of characteristic c if for any nonempty w ∈ S, the graph E(w) is a tree and if E(ε) is a union of c trees. Note that a tree set of characteristic c is a neutral set of characteristic c. A tree set of characteristic 1, simply called a tree set as in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF], is such that E(w) is a tree for any w ∈ S.

As an example, a Sturmian set is a tree set [START_REF] Berthé | Acyclic, connected and tree sets[END_REF] . Let S be a set of words. For w ∈ S, let

Γ S (w) = {x ∈ S | wx ∈ S ∩ A + w}. If S is recurrent, the set Γ S (w) is nonempty. Let Ret S (w) = Γ S (w) \ Γ S (w)A +
be the set of return words to w.

Note that a recurrent set S is uniformly recurrent if and only if the set Ret S (w) is finite for any w ∈ S. Indeed, if N is the maximal length of the words in Ret S (w) for a word w of length n, any word in S of length N + n contains an occurrence of w. The converse is obvious.

We will use the following result [START_REF] Berthé | Acyclic, connected and tree sets[END_REF]Theorem 4.5] . We denote by F A the free group on A.

Theorem 2.2 (Return Theorem). Let S be a uniformly recurrent tree set. For any w ∈ S, the set Ret S (w) is a basis of the free group F A .

Note that this result implies in particular that for any w ∈ S, the set Ret S (w) has Card(A) elements.

Example 2.6. Let S be the Tribonacci set. It is the set of factors of the infinite word x = abacaba • • • which is the fixed point of the morphism f defined by [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF]). We have Ret S (a) = {a, ba, ca}.

f (a) = ab, f (b) = ac, f (c) = a. It is a Sturmian set (see

Automata

All automata considered in this paper are deterministic and strongly connected and we simply call them automata. An automaton on a finite set Q of states is given by a partial map from Q × A into Q denoted p → p • a, and extended to words with the same notation. For a word w, we denote by ϕ A the map

p ∈ Q → p • w ∈ Q.
The transition monoid of the automaton A is the monoid M of partial maps from Q to itself of the form ϕ A (w) for w ∈ A * . The rank of an element m of M is the cardinality of its image, denoted Im(m).

Let A be an automaton and let S be a set of words. Denote by rank A (w) the rank of the map ϕ A (w), also called the rank of w with respect to the automaton A. The S-minimal rank of A is the minimal value of rank A (w) for w ∈ S. It is denoted rank A (S). A word of rank 1 is called synchronizing.

The following result gives a method to compute rank A (S) and thus gives a method to decide if A admits synchronizing words. Theorem 3.1. Let S be a recurrent set and let A be an automaton. Let w be in S and let I = Im(w). Then w has rank equal to rank A (S) if and only if rank A (wz) = rank A (w) for any z ∈ Ret S (w).

Proof. Assume first that rank A (w) = rank A (S). If z is in Ret S (w), then wz is in S. Since rank A (wz) ≤ rank A (w) and since rank A (w) is minimal, this forces rank A (wz) = rank A (w).

Conversely, assume that w satisfies the condition. For any r ∈ Ret S (w), we have I • r = Im(wr) ⊂ Im(w) = I. Since rank A (wr) = rank A (w), this forces I • r = I. Since Γ S (w) ⊂ Ret S (w) * , this proves that

Γ S (w) ⊂ {z ∈ S | I • z = I}. (3.1)
Let u be a word of S of minimal rank. Since S is recurrent, there exists words v, v ′ such that wvuv ′ w ∈ S. Then vuv ′ w is in Γ S (w) and thus I • vuv ′ w = I by (3.1). This implies that rank A (u) ≥ rank A (vuv ′ w) = rank A (w). Thus w has minimal rank in S.

Theorem 3.1 can be used to compute the S-minimal rank of an automaton in an effective way for a uniformly recurrent set S provided one can compute effectively the finite sets Ret S (w) for w ∈ S.

Example 3.1. Let S be the Fibonacci set and let A be the automaton given by its transitions in Figure 3.1 on the left. One has Im(a 2 ) = {1, 2, 4}. The action on the 3-element sets of states of the automaton is shown on the right. By Theorem 3.1, we obtain rank A (S) = 3. We denote by L, R, D, H the usual Green relations on a monoid M (see [START_REF] Berstel | Codes and Automata[END_REF]). Recall that R is the equivalence on M defined by The following result is proved in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] in a particular case (that is, for an automaton recognizing the submomoid generated by a bifix code). Proposition 3.2 Let S be a recurrent set and A be a strongly connected automaton. Set ϕ = ϕ A and M = ϕ(A * ). The set of elements of ϕ(S) of rank rank A (S) is included in a regular D-class of M .

mRn if mM = nM . The R-class of m is denoted R(m).
Proof. Set d = rank A (S). Let u, v ∈ S be two words of rank d. Set m = ϕ(u) and n = ϕ(v). Let w be such that uwv ∈ S. We show first that mRϕ(uwv) and nLϕ(uwv).

For this, let t be such that uwvtu ∈ S. Set z = wvtu. Since uz ∈ S, the rank of uz is d. Since Im(uz) ⊂ Im(z) ⊂ Im(u), this implies that the images are equal. Consequently, the restriction of ϕ(z) to Im(u) is a permutation. Since Im(u) is finite, there is an integer ℓ ≥ 1 such that ϕ(z) ℓ is the identity on Im(u). Set e = ϕ(z) ℓ and s = tuz ℓ-1 . Then, since e is the identity on Im(u), one has m = me. Thus m = ϕ(uwv)ϕ(s), and since ϕ(uwv) = mϕ(wv), it follows that m and ϕ(uwv) are R-equivalent.

Similarly n and ϕ(uwv) are L-equivalent. Indeed, let t ′ be such that vt ′ uwv ∈ S. Set z ′ = t ′ uwv. Then Im(vz ′ ) ⊂ Im(z ′ ) ⊂ Im(v). Since vz ′ is a factor of z 2 and z has rank d, it follows that d = rank(z 2 ) ≤ rank(vz ′ ) ≤ rank(v) = d. Therefore, vz ′ has rank d and consequently the images Im(vz ′ ), Im(z ′ ) and Im(v) are equal. There is an integer The D-class containing the elements of ϕ(S) of rank rank A (S) is called the Sminimal D-class of M . This D-class appears in a different context in [START_REF] Perrin | Automata on the integers, recurrence, distinguishability, and the equivalence of monadic theories[END_REF] (for a survey concerning the use of Green's relations in automata theory, see [START_REF] Colcombet | Green's relations and their use in automata theory[END_REF]). Let us recall some notions concerning groups in transformation monoids (see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] for a more detailed presentation). Let M be a transformation monoid on a set Q. For I ⊂ Q, we denote Let D be a regular D-class in a transformation monoid M on a set Q. The holonomy groups of M relative to the sets Qm for m ∈ D are all equivalent. The structure group of D is any of them.

ℓ ′ ≥ 1 such that ϕ(z ′ ) ℓ ′ is the identity on Im(v). Set e ′ = ϕ(z ′ ) ℓ ′ . Then n = ne ′ = nϕ(z ′ ) ℓ ′ -1 ϕ(tuwv) = nqϕ(uwv), with q = ϕ(z ′ ) ℓ ′ -1 ϕ(t). Since ϕ(uwv) = ϕ(uw)n,
Let A be an automaton with Q as set of states and let I ⊂ Q. Let w be a word such that ϕ A (w) ∈ Stab(I). The restriction of ϕ A (w) to I is a permutation which belongs to Group(I). It is called the permutation defined by the word w on the set I.

Let A be a strongly connected automaton and let S be a recurrent set of words. The S-group of A is the structure group of its S-minimal D-class. It is denoted G A (S).

For the set S = A * and a strongly connected automaton, the group G A (S) is a transitive permutation group of degree d X (S) (see [START_REF] Berstel | Codes and Automata[END_REF]Theorem 9.3.10]). We conjecture that it holds for a uniformly recurrent tree set. It is not true for any uniformly recurrent set S, as shown in the following examples. The fact that d A (S) = 3 and that G A (S) is trivial can be seen directly as follows. Consider the group automaton B represented in Figure 3.4 on the right and corresponding to the map sending each word to the difference modulo 3 of the number of occurrences of a and b. There is a reduction ρ from A onto B such that 1 → 0, 2 → 1, and 4 → 2. This accounts for the fact that d A (S) = 3. Moreover, one may verify that any return word x to a 2 has equal number of a and b (if x = uaa then aauaa is in S, which implies that aua and thus uaa have the same number of a and b). This implies that the permutation ϕ B (x) is the identity, and therefore also the restriction of ϕ A (x) to I. The same argument holds for Example 3.3 by considering the parity of the length.

Codes

A code is a set X such that for any n, m ≥ 0 any x 1 , . . . , x n and y 1 , . . . , y m in X, one has

x 1 • • • x n = y 1 • • • y m only if n = m and x 1 = y 1 ,..., x n = y n .
A prefix code is a set X of nonempty words which does not contain any proper prefix of its elements. A suffix code is defined symmetrically. A bifix code is a set which is both a prefix code and a suffix code.

Let S be a set of words. A prefix code X ⊂ S is said to be S-maximal if it is not properly contained in any prefix code Y ⊂ S. The notion of an S-maximal suffix or bifix code are symmetrical.

It follows from results of [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] that for a recurrent set S, a finite bifix code X ⊂ S is S-maximal as a bifix code if and only if it is S-maximal as a prefix code.

Given a set X ⊂ S, we denote λ S (X) = x∈X λ S (x) where λ S is the map defined by λ S (x) = e S (x) -r S (x). The following result is [START_REF] Dolce | Enumeration formulae in neutral sets[END_REF]Proposition 4]. Proposition 4.1 Let S be a neutral set of characteristic c on the alphabet A, and let X be a finite S-maximal prefix code. Then λ S (X) = Card(A) -c.

Symmetrically, one denotes ρ S (x) = e S (x) -ℓ S (x). The dual of Proposition 4.1 holds for suffix codes instead of prefix codes with ρ S instead of λ S .

Note that when S is Sturmian, one has λ S (x) = Card(A)-1 if x is left-special and λ S (x) = 0 otherwise. Thus Proposition 4.1 expresses the fact that any finite S-maximal prefix code contains exactly one left-special word [3, Proposition 5.1.5].

Example 4.1. Let S be the Fibonacci set and let X = {aa, ab, b}. The set X is an S-maximal prefix code. It contains exactly one left-special word, namely ab. Accordingly, one has λ S (X) = 1.

Let S be a factorial set and let X ⊂ S be a finite prefix code. The S-degree of X is the S-minimal rank of the minimal automaton of X * . It is denoted d X (S).

When X is a finite bifix code, the S-degree can be defined in a different way. A parse of a word w is a triple (s, x, p) such that w = sxp with s ∈ A * \ A * X, x ∈ X * and p ∈ A * \ XA * . For a recurrent set S and an S-maximal bifix code X, d X (S) is the maximal number of parses of a word of S. A word w ∈ S has d X (S) parses if and only if it is not an internal factor of a word of X (see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]).

The following result is [START_REF] Berthé | The finite index basis property[END_REF]Theorem 4.4].

Theorem 4.2 (Finite Index Basis Theorem). Let S be a uniformly recurrent tree set and let X ⊂ S be a finite bifix code. Then X is an S-maximal bifix code of S-degree d if and only if it is a basis of a subgroup of index d of F A .

Note that the result implies that any S-maximal bifix code of S-degree n has d(Card(A) -1) + 1 elements. Indeed, by Schreier's Formula, a subgroup of index d of a free group of rank r has rank d(r -1) + 1.

Example 4.2. Let S be a Sturmian set. For any n ≥ 1, the set X = S ∩ A n is an S-maximal bifix code of S-degree n. According to theorem 4.2, it is a basis of the subgroup which is the kernel of the group morphism from F A onto the additive group Z/nZ sending each letter to 1.

The following statement generalizes [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]Theorem 4.3.7] where it is proved for a bifix code (and in this case with a stronger conclusion).

Theorem 4.3. Let S be a recurrent set and let X be a finite S-maximal prefix code of S-degree n. The set of nonempty proper prefixes of X contains a disjoint union of n -1 S-maximal suffix codes.

Proof. Let P be the set of proper prefixes of X. Any word of S of rank n of length larger than the words of X has n suffixes which are in P .

We claim that this implies that any word in S is a suffix of a word with at least n suffixes in P . Indeed, let x ∈ S be of minimal rank. For any w ∈ S, since S is recurrent, there is some u such that xuw ∈ S. Then xuw is of rank n and has n suffixes in P . This proves the claim.

Let Y i for 1 ≤ i ≤ n be the set of p ∈ P which have i suffixes in P . One has Y 1 = {ε} and each Y i for 2 ≤ i ≤ d is clearly a suffix code. It follows from the claim above that it is S-maximal. Since the Y i are also disjoint, the result follows.

Corollary 1. Let S be a recurrent neutral set of characteristic c, and let X be a finite S-maximal prefix code of S-degree n. The set P of proper prefixes of X satisfies ρ S (P ) ≥ n(Card(A) -c). Proof. Let P be the set of proper prefixes of X. We may identify X with the set of leaves of a tree having P as set of internal nodes, each having r S (p) sons. By a well-known argument on trees, we have Card(X) = 1 + p∈P (r S (p) -1). Thus Card(X) = 1 + ρ S (P ). By Corollary 1, we have ρ S (P ) ≥ n(Card(A) -c).

The next example shows that the prefix code can have strictly more than d X (S)(Card(A) -c) + 1 elements. code X is S-maximal. The word ab has rank 2 in the literal automaton of X * . Indeed, Im(ab) = {1, 3}. Moreover R S (ab) = {ab, aab}. The ranks of abab and abaab are also equal to 2, as shown in Figure 4.2 on the right. Thus the S-degree of X is 2 by Proposition 3.1. The code X is not bifix since ba is a suffix of aaba.

The group of a bifix code

The following result is proved in [ The S-group of a prefix code, denoted G X (S), is the group G A (S) where A is the minimal automaton of X * . Theorem 4.5. Let Z be a group code of degree d and let S be a uniformly recurrent tree set S. The set X = Z ∩ S is an S-maximal bifix code of S-degree d and G X (S) is equivalent to the representation of F A on the cosets of the subgroup generated by X.

Proof. The first part is [7, Theorem 5.10], obtained as a corollary of the Finite Index Basis Theorem. To see the second part, let H be the subgroup generated by X of the free group F A . Consider a word w ∈ S which is not an internal factor of X. Let P be the set of proper prefixes of X which are suffixes of w. Then P has d elements since for each p ∈ P , there is a parse of w of the form (s, x, p). Moreover P is a set of representatives of the right cosets of H. Indeed, let p, q ∈ P and assume that p = uq with u ∈ S. If p ∈ Hq, then u ∈ X * ∩ S. Since p cannot have a prefix in X, we conclude that p = q. Since H has index d, this implies the conclusion.

Let A = (Q, i, i) be the minimal automaton of X * . Set I = Q • w. Let Stab(I) be the set of words x ∈ A * such that I • x = I. Note that Stab(I) contains the set Ret S (w) of right return words to w. For x ∈ Stab(I), let π(x) be the permutation defined by x on I. By definition, the group G X (S) is generated by π(Stab(I)). Since Stab(I) contains Ret S (w) and since Ret S (w) generates the free group F A , the set Stab(I) generates F A .

Let x ∈ Stab(I). For p, q ∈ I, let u, v ∈ P be such that i • u = p, i • v = q. Let us verify that p • x = q ⇔ ux ∈ Hv. is the set {1, 2}. We have Ret S (a) = {a, ba} and the action of Ret S (a) on the minimal images is indicated in Figure 4.3 on the right. The word a defines the permutation [START_REF] Perrin | Automata on the integers, recurrence, distinguishability, and the equivalence of monadic theories[END_REF] and the word ba the identity. Theorem 4.5 is not true for an arbitrary minimal set instead of a minimal tree set (see Example 3.4). The second part is true for an arbitrary finite S-maximal bifix code by the Finite Index Basis Theorem. We have no example where the second part is not true when X is S-maximal prefix instead of S-maximal bifix.

Example 2 . 2 .

 22 Let A = {a, b} and let f : A * → A * be the Fibonacci morphism defined by f (a) = ab and f (b) = a. The infinite word x = lim n→∞ f n (a) is the Fibonacci word. One has x = abaababa • • • . The Fibonacci set is the set of factors of the Fibonacci word. It is a Sturmian set, and thus a neutral set.

Example 2 . 4 .

 24 The set S of Example 2.1 is a tree set of characteristic 2.

Example 2 . 5 .

 25 Let A = {a, b} and let f : A * → A * be the morphism defined by f (a) = ab and f (b) = ba. The infinite word x = lim n→∞ f n (a) is the Thue-Morse word. The Thue-Morse set is the set of factors of the Thue-Morse word. It is uniformly recurrent but it is not a tree set since E(ε) = A × A.

Fig. 3 . 1 .

 31 Fig. 3.1. An automaton of S-degree 3.

  Symmetrically, one denotes by L the equivalence defined by mLn if M m = M n. It is well-known that the equivalences R and L commute. The equivalence RL = LR is denoted D. Finally, one denotes by H the equivalence R ∩ L.

  one has nLϕ(uwv). Thus m, n are D-equivalent, and ϕ(uwv) ∈ R(m) ∩ L(n). Set p = ϕ(wv). Then p = ϕ(w)n and, with the previous notation, n = ne ′ = nqϕ(u)p, so L(n) = L(p). Thus mp = ϕ(uwv) ∈ R(m) ∩ L(p), and by Clifford and Miller's Lemma, R(p) ∩ L(m) contains an idempotent. Thus the D-class of m, p and n is regular.

Example 3 . 2 .

 32 Let S be the Fibonacci set and let A be the automaton represented in Figure 3.2 on the left. The S-minimal D-class of the transition monoid of A is represented in Figure 3.2 on the right.

b * ba * ba 2 1, 2 , 3 *Fig. 3 . 2 .

 22332 Fig. 3.2. The automaton A and the S-minimal D-class

  Stab M (I) = {x ∈ M | Ix = I} or Stab(I) if the monoid M is understood. The holonomy group of M relative to I is the restriction of the elements of Stab M (I) to the set I. It is denoted Group(I).

Example 3 . 3 .

 33 Let S be the set of factors of (ab) * and let A be the automaton of Figure3.3. The minimal S-rank of A is 2 but the group G A (S) is trivial.

Fig. 3 . 3 .

 33 Fig. 3.3. An automaton of S-rank 2 with trivial S-group

Fig. 3 . 4 .Fig. 3 . 5 .

 3435 Fig. 3.4. An automaton of S-degree 3 with trivial S-group

Proof.

  By Theorem 4.3, there exist n -1 pairwise disjoint S-maximal suffix codes Y i (2 ≤ i ≤ n) such that P contains all Y i . By the dual of Proposition 4.1, we have ρ S (Y i ) = Card(A) -c for 2 ≤ i ≤ n. Since ρ S (ε) = e S (ε) -ℓ S (ε) = m S (ε)+r S (ε)-1 = Card(A)-c, we obtain ρ S (P ) ≥ ρ S (ε)+(n-1)(Card(A)-c) = n(Card(A) -c). 4.1 A cardinality theorem for prefix codes Theorem 4.4. Let S be a uniformly recurrent neutral set of characteristic c. Any finite S-maximal prefix code has at least d X (S)(Card(A) -c) + 1 elements.

Example 4 . 3 .Fig. 4 . 1 .Fig. 4 . 2 .

 434142 Fig. 4.1. A prefix code of S-degree 3

(4. 1 )Fig. 4 . 3 .

 143 Indeed, let t ∈ S be such that vt ∈ X. Then, one has p • x = q if and only if uxt ∈ X * which is equivalent to ux ∈ Hv. Since Stab(I) generates F A , Equation (4.1) shows that the bijection u → i • u from P onto I defines an equivalence from G X (S) onto the representation of F A on the cosets of H. Example 4.5. Let S be the Fibonacci set and let Z = A 2 which is a group code of degree 2 corresponding to the morphism from A * onto the additive Z/2Z sending each letter to 1. Then X = {aa, ab, ba}. The minimal automaton of X * is represented in Figure4.3 on the left. The word a has 2 parses and its image The minimal automaton of X * and the action on minimal images.

  3, Theorem 7.2.5] for a Sturmian set S. Recall that a group code of degree d is a bifix code Z such that Z * = ϕ -1 (K) for a surjective morphism ϕ from A * onto a finite group G and a subgroup K of index d in G. Equivalently, a bifix code Z is a group code if it generates the submonoid H ∩ A * where H is a subgroup of index d of the free group F A .


Matthew Trager

Brian Osserman

Jean Ponce

On the Solvability of Viewing Graphs

Keywords: Viewing graph, fundamental matrix, 3D reconstruction

A set of fundamental matrices relating pairs of cameras in some configuration can be represented as edges of a "viewing graph". Whether or not these fundamental matrices are generically sufficient to recover the global camera configuration depends on the structure of this graph. We study characterizations of "solvable" viewing graphs, and present several new results that can be applied to determine which pairs of views may be used to recover all camera parameters. We also discuss strategies for verifying the solvability of a graph computationally.

Introduction

Multi-view geometry has been studied by photogrammeters since the 1950s [START_REF]Manual of Photogrammetry[END_REF] and by computer vision researchers since the 1980s [START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF]. Still, most results to date are concerned with using multi-view tensors to characterize feature correspondences in 2, 3, or 4 views, and determine the corresponding projection matrices [START_REF] Hartley | Computation of the quadrifocal tensor[END_REF][START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF][START_REF] Luong | The fundamental matrix: theory, algorithms, and stability analysis[END_REF][START_REF] Shashua | [END_REF]. Although correspondences have also been characterized for arbitrary numbers of views [START_REF] Faugeras | On the geometry and algebra of the point and line correspondences between n images[END_REF][START_REF] Heyden | Algebraic properties of multilinear constraints[END_REF][START_REF] Triggs | Matching constraints and the joint image[END_REF], very little theoretical work has been devoted to understanding the geometric constraints imposed on configurations of n > 4 cameras by these tensors, including fundamental matrices [START_REF] Luong | The fundamental matrix: theory, algorithms, and stability analysis[END_REF], which are probably by far the most used in practice. Apart from a few works such as [START_REF] Levi | The viewing graph[END_REF][START_REF] Rudi | Linear solvability in the viewing graph[END_REF], understanding how many and which fundamental matrices can be used to recover globally consistent camera parameters is a largely unexplored problem.

We address this topic in this paper. Following [START_REF] Levi | The viewing graph[END_REF], we associate sets of fundamental matrices with edges of a "viewing graph", and present a series of new results for determining whether a graph is "solvable", i.e., whether it represents fundamental matrices that determine a unique camera configuration. We also describe effective strategies for verifying solvability, and include some computational experiments using these methods. Our focus here is clearly of a theoretical nature, but understanding how subsets of fundamental matrices constrain the reconstruction process is clearly important in practice as well. Moreover, we will point out that one of our main results (Theorem 3) is constructive, and could potentially find applications in reconstruction algorithms (e.g., it could be incorporated in large-scale systems such as [START_REF] Snavely | Photo tourism: Exploring image collections in 3D[END_REF], that incrementally build up networks of cameras to estimate their parameters).

Previous work. The first investigation of viewing graphs and their solvability can be found in [START_REF] Levi | The viewing graph[END_REF]. In that work, Levi and Werman characterize all solvable viewing graphs with at most six vertices, and discuss a few larger solvable examples. Although they provide some useful necessary conditions (see our Proposition 2 and Example 2), they do not address the problem of solvability in general. In [START_REF] Rudi | Linear solvability in the viewing graph[END_REF], Rudi et al. also consider viewing graphs, studying mainly whether a configuration can be recovered from a set of fundamental matrices using a linear system. They also present some "composition rules" for merging solvable graphs into larger ones. Trager et. al [START_REF] Trager | The joint image handbook[END_REF] provide a sufficient condition for solvability using 2n -3 fundamental matrices, and point to a possible connection with "Laman graphs" and graph rigidity theory. Indeed, Özyesil and Singer [START_REF] Ozyesil | Robust camera location estimation by convex programming[END_REF] show that if one uses essential matrices instead of fundamental ones then solvability can be characterized in terms of so-called "parallel-rigidity" for graphs. Their analysis however does not carry over to the more general setting of uncalibrated cameras. Finally, the viewing graph has also been considered in more practical work: for example, in [START_REF] Sinha | Camera network calibration and synchronization from silhouettes in archived video[END_REF][START_REF] Sweeney | Optimizing the viewing graph for structure-from-motion[END_REF], it is used to enforce triple-wise consistency among fundamental matrices before estimating camera parameters.

Main contributions.

• We show that the minimum number of fundamental matrices that can be used to recover a configuration of n cameras is always (11n -15)/7 (Theorem 1).

• We present several criteria for deciding whether or not a viewing graph is solvable. After revisiting some results from [START_REF] Levi | The viewing graph[END_REF][START_REF] Rudi | Linear solvability in the viewing graph[END_REF] (Section 3.1), we describe a new necessary condition for solvability that is based on the number of edges and vertices of subgraphs (Theorem 2), as well as a sufficient condition based on "moves" for adding new edges to a graph (Theorem 3).

• We describe an algebraic formulation for solvability that in principle can always be used to determine whether any viewing graph is solvable. Although this method is computationally challenging for larger graphs, we also introduce a much more practical linear test, that can be used to verify whether a viewing graph identifies a finite number of camera configurations (Section 4).

• Using an implementation of all the proposed methods, we analyze solvability for all minimal viewing graphs with at most 9 vertices. We also discuss some relevant examples (Section 5).

Background

To make our presentation mostly self-contained, we recall some basic theoretical facts that are used in the rest of the paper.

Notation. We write P n = P(R n+1 ) for the n-dimensional real projective space. We use bold font for vectors and matrices, and normal font for projective objects. For example, a point in P 3 will be written as p = [p] where p is a vector in R 4 and p is the equivalence class associated with p. Similarly, a projective transformation represented by a matrix M will be written as M = [M]. We use GL(n, R) for the group of n × n invertible real matrices.

Camera configurations and epipolar geometry

A projective camera P = [P] is represented by 3 × 4 matrix P of full rank, defined up to scale. The matrix P describes a linear projection P 3 \ {c} → P 2 where c = [c] is the pinhole of the camera, associated with the null-space of P.

The matrix group GL(4, R) acts on the set of cameras by multiplication on the right, and represents the group of projective transformations of P 3 , or of changes of homogeneous coordinates. We will use the fact that the group of matrices in GL(4, R) that fix a camera P = [P] with pinhole c = [c] is given by

Stab(P ) = {αI 4 + cv T | α ∈ R \ {0}, v ∈ R 4 } ∩ GL(4, R). (1)
Here Stab(P ) stands for "stabilizer". Indeed, all the solutions for M in PM = αP are described by [START_REF] Aholt | A hilbert scheme in computer vision[END_REF]. Note that Stab(P ) only depends on the pinhole of P . The following important fact follows directly from the form of Stab(P ).

Lemma 1. Given two cameras P 1 , P 2 with distinct pinholes, we have that

Stab(P 1 ) ∩ Stab(P 2 ) = {αI 4 , | α ∈ R \ {0}}. (2)
In other words, the identity is the only projective transformation that fixes both P 1 and P 2 .

Two sets of cameras (P 1 , . . . , P n ) and (P 1 , . . . , P n ) with P i = [P i ], P i = [P i ] are projectively equivalent if there exists a single projective transformation T such that P i = P i T (so if T = [T] with T in GL(4, R), then P i = α i P i T for non-zero constants α i ). The set of configurations of n cameras is the set of n-tuples of cameras up to projective equivalence. For any n ≥ 2, the space of camera configurations can be viewed as a manifold of dimension 11n -15.

Given two cameras P 1 = [P 1 ], P 2 = [P 2 ], the associated fundamental matrix F (P 1 , P 2 ) = [F] can be defined as the 3 × 3 matrix (up to scale) with entries

f il = (-1) i+l det(P T 1j P T 1k P T 2m P T 2n ), (3)
where P ar denotes the r-th row of P a , and (i, j, k) and (l, m, n) are triples of distinct indices. The fundamental matrix can be used to characterize pairs of corresponding points in the two images, since u 1 = [u 1 ] and u 2 = [u 2 ] are projections of the same 3D point if and only if u T 1 Fu 2 = 0. For our purposes, the most important property of the fundamental matrix is that it is invariant under projective transformations, and that F (P 1 , P 2 ) uniquely identifies the configuration of P 1 and P 2 [6, Theorem 9.10].

Finally, viewed as a subset of P 8 , the (closure of the) set of all fundamental matrices forms a hypersurface defined by det(F) = 0. If F (P 1 , P 2 ) = [F], the left and right null-space of F represent the two epipoles e 12 = P 1 c 2 and e 21 = P 2 c 1 , which are the images of each pinhole viewed from the other camera. An epipole accounts for two of seven degrees of freedom of a fundamental matrix. In fact, the information encoded in the fundamental matrix can be seen as the pair of epipoles e 12 , e 21 , together with a projective transformation P 1 → P 1 (known as "epipolar line homography" [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]) between lines containing e 12 in the first image and the lines containing e 21 in the second image. In particular, the knowledge of two epipoles together with three point correspondences completely determines a fundamental matrix.

The viewing graph

The viewing graph is a graph in which vertices correspond to cameras, and edges represent fundamental matrices between them. More precisely, if G = (V G , E G ) is an undirected graph with n vertices, and P 1 , . . . , P n are projective cameras, we write

F G (P 1 , . . . , P n ) = {F ij = F (P i , P j ) | (i, j) ∈ E G }, (4)
for the set of fundamental matrices defined by the edges of G. We say that the the set F G (P

P i = [P i (I 4 + c j v T )]
, where c j = [c j ] is the pinhole of another camera and v T is arbitrary, yields a new set of cameras which belongs to a different configuration but has the same set of fundamental matrices. Conversely, it is known (see for example [START_REF] Heyden | Algebraic properties of multilinear constraints[END_REF][START_REF] Trager | The joint image handbook[END_REF]) that the complete set of fundamental matrices determines a unique camera configuration whenever there are at least three non-aligned pinholes. ♦

In the rest of the paper we will only consider generic configurations of cameras/pinholes (so a complete graph will always be solvable). This covers most cases of practical interest, although in the future degenerate configurations (including some collinear or coplanar pinholes) could be studied as well. Definition 1. A viewing graph G is said to be solvable if F G (P 1 , . . . , P n ) is solvable for generic cameras P 1 , . . . , P n .

In other words, solvable viewing graphs describe sets of fundamental matrices that are generically sufficient to recover a camera configuration. Despite its clear significance, the problem of characterizing which viewing graphs are solvable has not been studied much, and only partial answers are available in the literature (mainly in [START_REF] Levi | The viewing graph[END_REF][START_REF] Rudi | Linear solvability in the viewing graph[END_REF]). It is quite easy to produce examples of graphs that are solvable, but it is much more challenging, given a graph, to determine whether it is solvable or not. The following observation provides another useful formulation of solvability (note that the "if" part requires the genericity assumption, as shown in Example 1). Lemma 2. A viewing graph G is solvable if and only if, for generic cameras P 1 , . . . , P n , the fundamental matrices

F G (P 1 , . . . , P n ) = {F (P i , P j ) | (i, j) ∈ E G } uniquely determine the remaining fundamental matrices {F (P i , P j ) | (i, j) ∈ E G }.
This viewpoint also suggests the idea that, given any graph G, we can define a "solvable closure" G, as the graph obtained from G by adding edges corresponding to fundamental matrices that can be deduced generically from F G (P 1 , . . . , P n ). Hence, a graph is solvable if and only if its closure is a complete graph. We will return to this point in Section 3.4.

Simple criteria

We begin by recalling two necessary conditions for solvability that were shown in [START_REF] Levi | The viewing graph[END_REF]. These provide simple criteria to show that a viewing graph is not solvable.

Proposition 2.

[10] If a viewing graph with n > 3 vertices is solvable, then: 1) All vertices have degree at least 2. 2) No two adjacent vertices have degree 2.

We extend this result with the following necessary condition (which implies the first point in the previous statement).

Proposition 3. Any solvable graph is 2-connected, i.e., it has the property that after removing any vertex the graph remains connected.

Proof. Assume that a vertex i disconnects the graph G into two components G 1 , G 2 , and let P 1 , . . . , P n be a set of n generic cameras, whose pairwise fundamental matrices are represented by the edges of G. If c i = [c i ] is the pinhole of the camera P i associated with i, then we consider two distinct projective transformations of the form

T 1 = [I 4 + α 1 c i v T 1 ] and T 2 = [I 4 + α 2 c i v T 2 ]
. These transformations fix the camera P i . If we apply T 1 to all cameras in G 1 and T 2 to all cameras in G 2 , while leaving P i fixed, we obtain a different camera configuration that gives rise to the same set of fundamental matrices as P 1 , . . . , P n for all edges in G.

We also recall a result from [START_REF] Rudi | Linear solvability in the viewing graph[END_REF] which will be used in the next section. Proposition 4. [START_REF] Rudi | Linear solvability in the viewing graph[END_REF] If G 1 and G 2 are solvable viewing graphs, then the graph G obtained by identifying two vertices from G 1 and with two from G 2 is solvable.

Note that if both pairs of vertices in the previous statement are connected by edges in G 1 and G 2 , then these two edges will automatically be identified in G.

How many fundamental matrices?

We now ask ourselves what is the minimal number of edges that a graph must have to be solvable (or, equivalently, how many fundamental matrices are required to recover a camera configuration). Since a single epipolar relation provides at most 7 constraints in the (11n-15)-dimensional space camera configuration, we deduce that any solvable graph must have at least e(n) = (11n-15)/7) edges. This fact was previously observed in [START_REF] Rudi | Linear solvability in the viewing graph[END_REF]Theorem 2]. However, compared to [START_REF] Rudi | Linear solvability in the viewing graph[END_REF], we show here that this bound is tight, i.e., that there always exists a solvable graph with e = e(n) edges. Concretely, this means that, for n generic views, there is always a way of recovering the corresponding camera configuration using e(n) fundamental matrices.

Theorem 1. The minimum number of edges of a solvable viewing graph with n ≥ 2 views is

e(n) = 11n -15 7 .
Proof. For n ≤ 9, examples of solvable viewing graphs with e(n) edges are illustrated Figure 1. The solvability of these graphs will be shown in Section 3.4 (all but one of these also appear in [START_REF] Levi | The viewing graph[END_REF]). In particular, let G 0 be a solvable viewing graph with 9 vertices and 12 edges. Using Proposition 4, we deduce that, starting from a solvable viewing graph G with n vertices and e edges, we can always construct a solvable graph G with n + 7 vertices and e + 11 edges. The graph G is simply obtained by merging G and G 0 as in Proposition 4, using two pairs of vertices both connected by edges. Now, for any n > 9, we consider the unique integers q, r such that n = 7q + r and 2 ≤ r ≤ 8. It is easy to see that e(n) = 11n -15 7 = 11q + 11r -15 7 .

To obtain a solvable viewing graph with n vertices and e(n) edges, we start from a solvable graph with r vertices and e(r) edges, and repeat the gluing construction described above q times. The resulting graph is solvable and has the desired number of vertices and edges.

Remark 1. It is worth pointing out that, in order to recover projection matrices for n views, it is quite common to use 2n -3 fundamental matrices (see for example [START_REF] Heyden | Tensorial properties of multiple view constraints[END_REF]Sec.4.4]). In fact, as shown in [START_REF] Trager | The joint image handbook[END_REF]Proposition 7], a large class of solvable viewing graphs can be defined, starting for example from a 3-cycle, by adding vertices of degree two, one at the time: this always gives a total of 2n -3 edges. For this type of viewing graphs it is possible to recover projection matrices incrementally, using a pair of fundamental matrices for each camera. In fact, it is probably quite often erroneously believed that 2n -3 is the minimal number of fundamental matrices that are required for multi-view reconstruction. Part of the confusion may arise from the fact that the "joint image" [START_REF] Triggs | Matching constraints and the joint image[END_REF][START_REF] Trager | The joint image handbook[END_REF][START_REF] Aholt | A hilbert scheme in computer vision[END_REF], which characterizes multi-view point correspondences in (P 2 ) n , has dimension three (or codimension 2n -3). This means means that we expect 2n -3 conditions to be necessary to cut out generically the set of image correspondences among n views. On the other hand, according to Theorem 1, fewer constraints are actually sufficient to determine camera geometry. 4Some values of e(n) are listed in Table 1 (here d(n) represents the minimal number of constraints on the fundamental matrices, and will be discussed in the next section). Note that e(n) < 2n -3 for all n ≥ 5.

Constraints on fundamental matrices

Closely related to the solvability of viewing graphs is the problem of describing compatibility of fundamental matrices. Indeed, given a solvable graph G, it is not true in general that any set of fundamental matrices can be assigned to the edges of G, since fundamental matrices must satisfy some feasibility constraints in order to correspond to an actual camera configuration. For example, it is well known that the fundamental matrices F

where e ij = [e ij ] is the epipole in image i relative to the camera j [6, Theorem 15.6]. In most practical situations fundamental matrices are estimated separately, so these constraints need to be taken into account [START_REF] Sweeney | Optimizing the viewing graph for structure-from-motion[END_REF]. However, it is sometimes incorrectly stated that compatibility for any set of fundamental matrices only arises from triples and equations of the form (5) [15, Theorem 1], [20, Definition 1]. While it is true that for a complete set of n 2 fundamental matrices triple-wise compatibility is sufficient to guarantee global compatibility, for smaller sets of fundamental matrices other types of constraints will be necessary. For example, there are many solvable viewing graphs with no three-cycles (e.g., the graph in Figure 1 with n = 5), however the fundamental matrices cannot be unconstrained if 7e(n) > 11n -15, which always true unless e = 2 modulo 9 (cf. Table 1).

More formally, we can consider the set X of compatible fundamental matrices between all pairs of n views, so that X ⊂ (P 8 ) N where N = n 2 . Since each compatible N -tuple is associated with a camera configuration, we see that X has dimension 11n-15. Given a viewing graph G with n views, we write X G ⊂ (P 8 ) e for the projection of X onto the factors in (P 8 ) N corresponding to the edges of G. The set X G thus represents compatible fundamental matrices for pairs of views associated with the edges of G. The following result follows from dimensionality arguments (see the supplementary material for a complete proof).

Proposition 5. If G is solvable with n vertices, X G has dimension 11n -15.
If X G has dimension 11n -15, then the fundamental matrices assigned to the edges of G must satisfy d(n, e) = 7e -11n + 15 constraints 5 . This also means that the minimum number of constraints on the fundamental matrices associated with a solvable graph is d(n) = d(n, e(n)) (see Table 1).

We now use Proposition 5 to deduce a new necessary condition for solvability.

Theorem 2. Let G be a solvable graph with n vertices and e edges. Then for any subgraph G of G with n vertices and e edges we must have

d(n , e ) ≤ d(n, e), (6)
where d(n, e) = 7e -11n + 15. More generally, if G 1 , . . . , G k are subgraphs of G, each with n i vertices and e i edges, with the property that the edge sets E Gi ⊂ E G are pairwise disjoint, then we must have

k i=1 d(n i , e i ) ≤ d(n, e). (7)
Proof. Using the same notation as above, we note that that X G is a projection of X G onto e factors of (P 8 ) e : this implies dim

X G + 7(e -e ) ≥ dim X G , or 7e -dim X G ≤ 7e -dim X G . Since dim X G ≤ 11n -15 and dim X G = 11n -15 (because G is solvable), we obtain 7e -11n + 15 ≤ 7e -dim X G ≤ 7e -dim X G = 7e -11n + 15.
For the second statement, we consider the graph

G = ( i V Gi , i E Gi ). Since the edges of G i are disjoint, we have dim X G ≤ k i=1 dim X Gi ≤ k i=1 (11n i -15),
5 This is the codimension of XG in H e where H ⊂ P 8 is the determinant hypersurface.

and e = k i e i . The result follows again from 7e -dim X G ≤ 7e -dim X G . Example 2. In [START_REF] Levi | The viewing graph[END_REF], Levi and Werman observe that all viewing graphs of the form shown in Figure 2 are not solvable. This can be easily deduced from Theorem 2. Indeed, for a graph G of this form, the subgraphs G 1 , G 2 , G 3 , G 4 have disjoint edges, however we have (using the same notation as in the proof of Theorem 2)

4 i=1 d(n i , e i ) = d(n, e) -4 × 11 + 3 × 15 > d(n, e).
According to Theorem 2 this means that G is not solvable.

♦ G1 G2 G3 G4
Fig. 2. A viewing graph of this form (where G1, G2, G3, G4 represent arbitrary subgraphs) is not solvable

Constructive approach for verifying solvability

Until now we have mainly discussed necessary conditions for solvability, which can be used to show that a given graph is not solvable. We next introduce a general strategy for proving that a graph is solvable. This method is not always guaranteed to work, but in practice it gives sufficient conditions for most of the graphs we tested (cf. Section 5).

Recall from the beginning of this section that we introduced the "viewing closure" G of G as the graph obtained by adding to G all edges corresponding to fundamental matrices that can be deduced from F G (P 1 , . . . , P n ). Our approach consists of a series of "moves" which describe valid ways to add new edges to a viewing graph. For this it is convenient to introduce a new type of edge in the graph, which keeps track of the fact that partial information about a fundamental matrix is available. More precisely:

-A solid (undirected) edge between vertices i and j means that the fundamental matrix between the views i and j is fixed (as before). -A directed dashed edge (for short, a dashed arrow) between vertices i and j means that the i-th epipole in the image j is fixed.

As these definitions suggest, a solid edge also counts as a dashed doublearrow, but the converse is not true. We next introduce three basic "moves" (cf. Figure 3). Let G be a viewing graph. If applying the three moves described above iteratively to G we obtain a complete graph, then G is solvable.

Proof. For each of the three moves we need to show that the new edges contain information about the unknown fundamental matrices that can actually be deduced from F G (P 1 , . . . , P n ).

Move I: The second diagonal of the square is deducible from the other edges because the square with one diagonal is a solvable graph (this is a simple consequence of Proposition 4). Move II: Assume that e 21 = P 2 c 1 and e 32 = P 3 c 2 are fixed epipoles in images 2 and 3, and that the fundamental matrices F 24 = F (P 2 , P 4 ), F 34 = F (P 3 , P 4 ) are also fixed. If c 1 , c 2 , c 4 are not aligned, we can use F 24 to "transfer" the point e 21 , and obtain a line l 41 in image 4 that contains epipole e 41 . Similarly, if c 1 , c 3 , c 4 are not aligned, we obtain another line m 41 using the same procedure with F 34 and e 31 . If the pinholes c 1 , c 2 , c 3 , c 4 are not all coplanar, the lines l 41 and m 41 will be distinct, and their point of intersection will be e 41 . This implies that we can draw a dashed arrow from 1 to 4. Move III: Assume that the epipoles e 21 and e 12 are fixed, and that the images of three other pinholes c 3 , c 4 , c 5 are fixed in both images 1 and 2. If the planes c 1 , c 2 , c i for i = 3, 4, 5 are distinct, then the images of c 3 , c 4 , c 5 give three correspondences that fix the epipolar line homography. This completely determines F 12 , and we can draw a solid edge between 1 and 2.

In practice, the three moves can be applied cyclically until no new edges can be added (it is also easy to argue the order is irrelevant, because we are simply annotating information that is always deducible from the graph). Finally, we note that all three moves are constructive and linear, meaning they actually provide a practical strategy for computing all fundamental matrices: it is enough to transfer epipoles appropriately, and use them to impose linear conditions on the unknown fundamental matrices. Given a viewing graph G, it is possible to write down a set of algebraic conditions that will in principle always determine whether G is solvable. One way to do this is by characterizing the set of projective transformations of P 3 that can be applied to all cameras without affecting any of the fundamental matrices represented by the edges of the viewing graph. More precisely, since every pair of vertices connected by an edge represents a projectively rigid pair of cameras, we assign a matrix g λ in GL(4, R) to each edge λ of the graph (so g λ describes a projective transformation applied to a pair of cameras). We then impose that matrices on adjacent edges act compatibly on the shared vertex/camera. If the edges λ and λ share a vertex i, then from [START_REF] Aholt | A hilbert scheme in computer vision[END_REF] we see that this compatibility can be written as

g λ g -1 λ = αI 4 + c i v T , ( 8
)
where α is an arbitrary (nonzero) constant and v is an arbitrary vector. Thus, if G is a viewing graph with e edges and c 1 , . . . , c n are a set of pinholes, we consider the set of all compatible assignments of matrices:

TG(c1, . . . , cn) = {(g λ , λ ∈ EG) | (8) holds for all adjacent edges in G} ⊂ GL(4, R) e .
If G is solvable, then for general c 1 , . . . , c n the set T G (c 1 , . . . , c n ) will consist of e-tuples of matrices that are all scalar multiples of each other. This in fact means that the only way to act on all cameras without affecting the fixed fundamental matrices is to apply a single projective transformation. By substituting random pinholes in [START_REF] Heyden | Tensorial properties of multiple view constraints[END_REF], we can use these equations for T G (c 1 , . . . , c n ) as an algebraic test for verifying whether a viewing graph is solvable. This approach however is computationally very challenging, since it requires solving a non-linear algebraic system with a large number of variables.

On the other hand, if we are only interested in the dimension of T G (c 1 , . . . , c n ), then we can use a much simpler strategy: noting that T G (c 1 , . . . , c n ) may be viewed as an algebraic group (it is a subgroup of GL(4, R) e ), it is sufficient to compute the dimension of its tangent space at any point, and in particular at the identity (i.e., the product of identity matrices). 6 An explicit representation of the tangent space of T G (c 1 , . . . , c n ) is provided by the following result (see the supplementary material for a proof). Proposition 6. The tangent space of T G (c 1 , . . . , c n ) at the identity can be represented as the space of e-tuple of matrices (h λ , λ ∈ E G ) where each h λ is in R 4×4 (not necessary invertible), and with compatibility conditions of the form

h λ -h λ = αI 4 + c i v T , ( 9
)
where α ∈ R \ {0} and v ∈ R 4 are arbitrary, and λ and λ share the vertex i.

When the pinholes have been fixed, the compatibility constraints ( 9) can be expressed as linear equations in the entries of the matrices h λ . These equations are obtained by eliminating the variables α and v from [START_REF] Heyden | Algebraic properties of multilinear constraints[END_REF]. The resulting conditions in terms of h λ , h λ , c i are rather simple, and listed explicitly in the supplementary material. Using this approach, the dimension of T G (c 1 , . . . , c n ) is easy to determine: it is enough to fix the pinholes randomly, and compute the dimension of the induced linear system.

When T G (c 1 , . . . , c n ) has dimension d = 15 + e (which accounts for the group of projective transformations, and scale factors for each matrix g λ ), we deduce that there are at most a finite number of projectively inequivalent ways in which we can act on all the cameras without affecting the fixed fundamental matrices. In other words, the fundamental matrices associated with the edges of G determine at most a finite set of camera configurations (rather than a single configuration, which is our definition for solvability). When this happens, we say that G is finite solvable. On the other hand, we were not able to find an example of a finite solvable graph that is provably not solvable, nor to find a proof that "finite solvability" implies "solvability". To our knowledge, whether a set of fundamental matrices can characterize a finite number of configurations, but more than a single one, is a question that has never been addressed.

Open Question. Is it possible for a viewing graph to be finite solvable without being solvable?

Our experiments show that this behavior does not occur for a small number of vertices, but we see no reason why this should be true for larger graphs. This is certainly an important issue that we hope to investigate in the future.

Experiments and examples

We have implemented and tested all of the discussed criteria and methods using the free mathematical software SageMath [START_REF] Developers | SageMath, the Sage Mathematics Software System[END_REF]. 7 We then analyzed solvability for all minimal viewing graphs with n ≤ 9 vertices and e(n) = (11n -15)/7 edges. The results are summarized in Table 5. For every pair (n, e(n)), we list the number of all non-isomorphic connected graphs of that size ("connected"), the number of graphs that satisfy the necessary condition from Theorem 2 ("candidates"), the number of those that satisfy the sufficient condition from Theorem 3 ("solvable with moves"), and the number of graphs that are finite solvable ("finite solvable"), using the linear method from 4. We see that Theorems 2 and 3 allow us to recover all minimal solvable graphs for n ≤ 7, since candidate graphs are always solvable with moves. On the other hand, for n = 8, and particularly for the unconstrained case n = 9, there are some graphs that we could not classify with those methods (although finite solvability was easy to verify in all cases). For the undecided graphs, we were sometimes able to prove solvability with the general algebraic method from Section 4, or using other arguments.

The following examples present a few interesting cases.

Table 2. Solvability of minimal viewing graphs using our methods Example 4. The graph shown in Figure 5 (left) is one of the five cases with n = 8, e = 11 that are "candidates" but are not "solvable with moves". However, we can show that this graph is actually solvable by arguing that the image of the pinhole 1 in the view 7 is fixed, even if this is not a consequence of the moves of Theorem 3 (this is represented by the gray dashed arrow in the figure). To prove this fact, one needs to keep track of more information, and record also when an epipole is constrained to a line (rather than only when an epipole is fixed, which is the purpose of dashed edges). 8 After drawing the dashed arrow from 1 to 7, solvability can be shown using the moves from Theorem 3. ♦ Example 5. The graph shown in Figure 5 (center) is the only viewing graph with n = 9 and e = 12 that is "candidate" but is not "finite solvable". The fact that it is not finite solvable can also deduced without computations. Indeed, any finite solvable viewing graph of this size cannot impose any constraints on 7 Our code is available at https://github.com/mtrager/viewing-graphs. 8 This information can be taken into account by defining a new type of edge together with additional moves. We did not do this in Theorem 3 because this type of edge is never necessary for smaller graphs.

(n, e(n)) (3,3) (4,5) (5,6) (6,8) (7,9) (8,11) (9,12) connected 1 1
the fundamental matrices associated with its edges (this is because d(9, 12) = 7×12-11×9+15 = 0). However, the image of the pinhole 7 in the view 2 is overconstrained, because we can draw a dashed arrow 7 → 2 using move II for two distinct four-cycles ((7, 1, 2, 5) and (7, 3, 2, 5)). This implies that the fundamental matrices associated with the edges of the graph cannot be arbitrary. ♦ Example 6. The graph shown in Figure 5 (right) is not "solvable with moves", however one can show that it is solvable: indeed, the general algebraic compatibility equations from Section 4 are in this case simple and can be solved explicitly (see the supplementary material for the computations). The fundamental matrices associated with the edges of the graph are unconstrained, so 12 arbitrary fundamental matrices determine a unique configuration of 9 cameras. ♦

Conclusions

We have studied the problem of solvability of viewing graphs, presenting a series of new theoretical results that can be applied to determine whether a graph is solvable. We have also pointed out some open questions (particularly, the relation between finite solvability and solvability, discussed in Section 4), and we hope that this paper can lead to further work on these issues.

Our main focus here was to understand whether the camera-estimation problem is well-posed, and we did not directly address the task of determining the configuration computationally. Properly recovering a global camera configuration that is consistent with local measurements is challenging, and is arguably the main obstacle for any structure-from-motion algorithm. For this reason, we believe that a complete understanding of the algebraic constraints that characterize the compatibility of fundamental matrices would be very useful. This is an issue that has not been considered much in classical multi-view geometry, and is very closely related to the topic of this paper. We plan to investigate it next. This supplementary material contains some technical discussions and examples that were not included in the main body of the paper.

A Solvability using algebraic geometry

It is useful to revisit solvability from a slightly more technical viewpoint. We let ϕ G : (P 11 ) n (P 8 ) e be the rational map associating to a set of cameras the fundamental matrices corresponding to the edges of G (so that e = |E G |). 9 The map ϕ G is rational because the coefficients of the fundamental matrix are polynomials in the entries of the two projection matrices. The (closure of the) image of this map is an algebraic variety in (P 8 ) e representing the set of "compatible" fundamental matrices that can be assigned to the edges of G. We denote this set with X G (as in the main part of the paper).

The solvability of the graph G can be understood in terms of ϕ G and X G . We will use the following general property of rational maps.

Proposition A.1. Let f : X → Y be rational map of projective varieties over an algebraically closed field, and let Z be the closure of the image of f . Then there exists a (Zariski) open dense neighborhood U of Z such that the fiber of f over U has always: 1) the same (pure) dimension dim X -dim Z, and 2) the same number of connected components.

Proof. The first point is [START_REF] Shafarevich | Basic algebraic geometry[END_REF]Theorem 7], the second one is [START_REF] Grothendieck | Éléments de géométrie algébrique iv[END_REF]Proposition 9.7.8]. This result states that, over an algebraically closed field, pre-images of general points will have the same dimension and the same number of connected components. In our setting, this implies that if we view ϕ G as a map on (CP 11 ) n , there exists an open dense set U G in its image that defines its general behavior, and one of the following holds:

1. the pre-image of every element in U G is a unique camera configuration, 2. the pre-image of every element in U G contains a fixed finite number r > 1 of (complex) camera configurations, 3. the pre-image of every element in U G contains infinitely many (complex) camera configurations.

Because uniqueness over C is stronger than uniqueness over R, we see that necessarily if 1 occurs, the graph G is solvable, and similarly if either 1 or 2 occur, G is finite solvable. On the other hand, it might be possible for G to be solvable in case 2, but this would require that exactly one of the r complex configurations in the general fiber is real.

The next result essentially shows that G is finite solvable if and only if we are in situations 1 and 2 (because if a set of fundamental is compatible with an infinite set of complex configurations, it is also compatible with an infinite set of real ones).

Proposition A.2. Suppose that we are in situation 3 above. Then there is a possibly smaller open dense subset U G ⊂ U G such that every real fiber either contains no real configurations or infinitely many real configurations. Moreover, the latter case occurs over a Zariski dense subset of U G .

Proof. According to the 2nd Bertini Theorem [16, Theorem 2], there is an open subset of the image of ϕ G over which the fibers are smooth. If these fibers have any real points, then the implicit function theorem from multivariable calculus implies that real points occur in dimension equal to the complex dimension.

As a corollary we obtain the following result (which implies Proposition 5 in the main part of the paper).

Proposition A.3. The graph G is finite solvable if and only if X G has dimension 11n -15.

Proof. It is sufficient to note that if 1 or 2 occur, the generic fiber of ϕ G has dimension 15 in (P 11 ) n . In situation 3, the fiber has higher dimension.

B Linear equations for finite solvability

We recall here that T G (c 1 , . . . , c n ) was defined in the main part of the paper as the set of e-tuples (g λ , λ ∈ E G ) of matrices in GL(4, R) which satisfied compatibility equations of the form

g λ g -1 λ = αI 4 + c i v T , ( 10
)
where α is an arbitrary (nonzero) constant and v is an arbitrary vector. The following result will be useful.

Proposition B.1. If c = (c 0 , c 1 , c 2 , c 3
) is a non-zero vector, then a matrix M = (m ij ) i,j=0,...,3 can be written in the form M = αI 4 + cv T for some arbitrary α and v if and only if the following linear expressions vanish:

m31c2 -m21c3 m30c2 -m20c3 m32c1 -m12c3 m30c1 -m10c3 m23c1 -m13c2 m20c1 -m10c2 m32c0 -m02c3 m31c0 -m01c3 m23c0 -m03c2 m21c0 -m01c2 m13c0 -m03c1 m12c0 -m02c1 m22c1 -m33c1 -m12c2 + m13c3 m21c1 -m11c2 + m33c2 -m23c3 m30c0 -m32c2 -m00c3 + m22c3 m22c0 -m33c0 -m02c2 + m03c3 m20c0 -m00c2 + m33c2 -m23c3 m31c1 -m32c2 -m11c3 + m22c3 m11c0 -m33c0 -m01c1 + m03c3 m10c0 -m00c1 + m33c1 -m13c3. (11)
Proof. The result is easily shown using a computer algebra system. Inside the ring Q[m 00 , . . . , m 33 , c 0 , . . . , c 3 , v 0 , . . . , v 3 , α], we consider the ideal I obtained by eliminating the variables v 0 , v 1 , v 2 , v 3 and α from the coordinates of M -αI 4 + cv T . We can then verify that (11) generate an ideal that decomposes into two prime components: one of these is irrelevant for us (it describes the vanishing of c) and the other one is I.

We can now prove Proposition 6 from the main part of the paper. Proposition 6. The tangent space of T G (c 1 , . . . , c n ) at the identity can be represented as the space of e-tuples of matrices (h λ , λ ∈ E G ) where each h λ is in R 4×4 (not necessary invertible), and with compatibility conditions of the form

h λ -h λ = αI 4 + c i v T , (12)
where α ∈ R \ {0} and v ∈ R 4 are arbitrary, and λ and λ share the vertex i.

Proof. According to Proposition B.1, a matrix M can be written in the form M = αI 4 + cv T for some α ∈ R \ {0} and v ∈ R 4 if and only if it satisfies a set linear equations that depend on c. Let us write L c (M) = 0 for these linear conditions (so L c is a linear map). Note that necessarily L c (I 4 ) = 0.

A constraint of the form [START_REF] Levi | The viewing graph[END_REF] can now be expressed as F (g λ , g λ ) = L c (g λ g -1 λ ) = 0. Writing the first order expansion or F (g λ , g λ ) = 0 at (I 4 , I 4 ) we obtain (≈ denotes equality up to higher order terms)

F (I 4 + h λ , I 4 + h λ ) ≈ L c ((I 4 + h λ )(I 4 -h λ )) ≈ L c (h λ -h λ ). ( 13
)
This shows that L c (h λ -h λ ) = 0 is the tangent space at the identity of each constraint [START_REF] Levi | The viewing graph[END_REF]. By Proposition B.1 we have that L c (h λ -h λ ) = 0 is equivalent to [START_REF] Luong | The fundamental matrix: theory, algorithms, and stability analysis[END_REF], and this concludes the proof.

Finally, we note that by substituting M = h λ -h λ inside [START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF], we obtain explicit equations that can be used to determine finite solvability (as explained in Section 4 of the paper).

C Examples

Example C.1. Let G be the four-cycle shown in Figure 6. We immediately see that the graph is not solvable, because a solvable graph with four vertices must have at least e(4) = 5 edges. It is however useful to understand this example algebraically. Following the general approach described in Section 4 of the paper, we assign the identity I 4 to the edge (1, 2), and unknown matrices g (2,3) , g [START_REF] Faugeras | On the geometry and algebra of the point and line correspondences between n images[END_REF][START_REF] Grothendieck | Éléments de géométrie algébrique iv[END_REF] , g [START_REF] Aholt | A hilbert scheme in computer vision[END_REF][START_REF] Grothendieck | Éléments de géométrie algébrique iv[END_REF] to the remaining edges. The compatibility equations yield

g (1,4) = α 1 I 4 + c 1 v T 1 g (2,3) = α 2 I 4 + c 2 v T
where Example C.3. Let G be the graph shown in Figure 8. As argued in the main part of the paper (Example 4), we can show that this graph is solvable by proving that the image of the pinhole 1 in the view 7 is fixed by the structure of the graph. Indeed, we note that:

w 1 = α 4 v 1 , w 2 = -α 3 v 2 , w 3 = -(α 2 I 4 + v 2 c T 2 )v 3 , w 4 = (α 1 I 4 + v 1 c T 1 )v 4 , (17)
1. The image of the pinhole 1 in the view 5 lies on the line l 51 defined by reprojection of the epipole e 41 from the view 4 to the view 5. 2. Similarly, the image of the pinhole 1 in the view 6 lies on the line l 61 defined by the reprojection of the epipole e 31 from the view 3 to the view 6. 3. Using the previous two observations, we deduce that the image of the pinhole 1 in the view 7 lies on the line l 71 obtained by transferring l 51 and l 61 to the view 7. This line is the projection from 7 of the intersection of the planes spanned by c 1 , c 4 , c 5 and c 1 , c 3 , c 6 . 4. The image of the pinhole 1 in the view 7 belongs to another line m 71 that is the reprojection of the epipole e 81 from the view 8 to the view 7. 5. For generic pinholes the lines m 71 and l 71 will be different, so their intersection determines the image of the pinhole 1 in the view 7. This argument shows that we can draw a dashed arrow from the vertex 1 to the vertex 7. We can now prove that G is solvable using the following sequence of moves (which starts from the situation illustrated at the right of Figure 8).

-Draw double dashed arrows (4,7) and (3,7) (move II).

-Draw a dashed arrow from 1 to 5 (move II for the four-cycle [START_REF] Aholt | A hilbert scheme in computer vision[END_REF][START_REF] Grothendieck | Éléments de géométrie algébrique iv[END_REF][START_REF] Hartley | Computation of the quadrifocal tensor[END_REF][START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF]).

-Make (3,5) solid (move III), and then also [START_REF] Grothendieck | Éléments de géométrie algébrique iv[END_REF][START_REF] Hartley | Multiple view geometry in computer vision[END_REF], and (4,7) and (3,7) (move I). -Make (1,7) double dashed (move II for [START_REF] Aholt | A hilbert scheme in computer vision[END_REF][START_REF] Grothendieck | Éléments de géométrie algébrique iv[END_REF][START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF][START_REF] Heyden | Tensorial properties of multiple view constraints[END_REF]).

-Make (1,3) solid (move III) and complete the graph using move I. ♦

9 Fig. 1 .

 91 Fig. 1. Examples of minimal solvable viewing graphs for n ≤ 9 views (see Section 3.4)

(

  I) If there are solid edges defining a four-cycle with one diagonal, draw the other diagonal. (II) If there are dashed arrows 1 → 2, 1 → 3, and solid edges 2 -4 and 3 -4, draw a dashed arrow 1 → 4. (III) If there are double dashed arrows 1 ↔ 2, together with three pairs of dashed arrows i → 1, i → 2 for i = 3, 4, 5, make the arrow between 1 and 2 a solid (undirected) edge.

Fig. 3 .

 3 Fig. 3. Three moves (left: I, center: II, right: III) that can be used to prove solvability

Example 3 .Fig. 4 .

 34 Fig. 4. Two applications of Theorem 3 to prove that viewing graphs are solvable

Fig. 5 .

 5 Fig. 5. The graphs described in Examples 4, 5, 6

2 g ( 3 , 4 ) g - 1 ( 2 , 3 ) = α 3 I 4 + c 3 v T 3 g ( 3 , 4 ) g - 1 ( 1 , 4 ) = α 4 I 4 + c 4 v T 4 ( 14 )

 2341233433411444414 which imply thatg (3,4) = (α 3 I 4 + c 3 v T 3 )(α 2 I 4 + c 2 v T 2 ) = (α 4 I 4 + c 4 v T 4 )(α 1 I 4 + c 1 v T 1 ). (15)Expanding[START_REF] Rudi | Linear solvability in the viewing graph[END_REF] we obtain(α 3 α 2 -α 4 α 1 )I 4 = c 1 w T 1 + c 2 w T 2 + c 3 w T 3 + c 4 w T 4 ,

Fig. 6 .Fig. 7 .

 67 Fig. 6. The four-cycle from Example C.1

Fig. 8 .

 8 Fig. 8. The graph from Example C.3

  1 , . . . , P n ) is solvable if F G (P 1 , . . . , P n ) = F G (P 1 , . . . , P n ) implies that (P 1 , . . . , P n ) and (P 1 , . . . , P n ) are in the same projective configuration. In other words, a set of fundamental matrices is solvable if and only if it uniquely determines a projective configuration of cameras.Proposition 1. The solvability of F G (P 1 , . . . , P n ) only depends on the graph G and on the pinholes c 1 , . . . , c n of P 1 , . . . , P n .Proof. The statement expresses the fact that changes of image coordinates are only a relabeling of a camera configuration and the associated fundamental matrices. More precisely, if S 1 , . . . , S n are arbitrary projective transformations of P 2 , then (P 1 , . . . , P n ) and (P 1 , . . . , P n ) are in the same configuration if and only if the same is true for (S 1 P 1 , . . . , S n P n ) and (S 1 P 1 , . . . , S n P n ). This implies that F G (P 1 , . . . , P n ) is solvable if and only F G (S 1 P 1 , . . . , S n P n ) is.

	Example 1. If G is a complete graph with n ≥ 3 vertices, then F G (P 1 , . . . , P n ) is
	solvable if and only if the pinholes of the cameras P 1 , . . . , P n are not all aligned.
	Indeed, if the pinholes are aligned, then the fundamental matrices between all
	pairs of cameras are not sufficient to completely determine the configuration:
	replacing any P i = [P i ] with

Table 1 .

 1 The relation between n, e(n), and d(n)

	n 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
	e(n) 1 3 5 6 8 9 11 12 14 16 17 19 20 22 23

  12 , F 23 , F 31 relating three pairs of cameras with non-aligned pinholes are compatible if and only if e T 13 F 12 e 23 = e T 21 F 23 e 31 = e T 32 F 31 e 12 = 0,

This implies however that fewer than 2n -3 conditions can in fact determine a joint image in (P 2 ) n , at least "indirectly" through the camera configuration. Mathematically, this is an interesting phenomenon that could be investigated in the future.

Here we actually need that TG(c1, . . . , cn) is smooth: this follows from a technical result, which states that an algebraic group (more properly a "group scheme") over a field of characteristic zero is always smooth[START_REF] Mumford | Abelian Varieties[END_REF] Sec.11].

We recall that rational map between projective spaces is a map whose coordinates are homogeneous polynomial functions. The map is in general well-defined only on an open set of the domain. Note that the definition of ϕG actually requires fixing an orientation for each edge in G, since a fundamental matrix represents an ordered pair of cameras. However, it is easy to see that the orientations of the edges can be chosen arbitrarily.

Acknowledgments. This work was supported in part by the ERC grant Video-World, the Institut Universitaire de France, the Inria-CMU associated team GAYA, a collaboration agreement between Inria and NYU, and a grant from the Simons Foundation #279151.

From [START_REF] Shafarevich | Basic algebraic geometry[END_REF] we see that the vectors w i must be scalar multiples of the rows of the matrix C -1 where C has columns c 1 , c 2 , c 3 , c 4 . This easily implies that for fixed general coefficients α 1 , α 2 , α 3 , α 4 , there is a unique solution for v 1 , . . . , v 4 in [START_REF] Ozyesil | Robust camera location estimation by convex programming[END_REF]. Moreover, since the matrices g (i,j) represent projective transformations, we can rescale these equations so that for example α 1 = α 2 = α 3 = 1. This shows that there is one degree of projective freedom corresponding to the choice of α 4 . This projective freedom can also be explained in different ways: for example, our analysis implies that g (1,4) can be any matrix of the form g

Not counting the scale factor, this gives one degree of freedom, and fixing g [START_REF] Aholt | A hilbert scheme in computer vision[END_REF][START_REF] Grothendieck | Éléments de géométrie algébrique iv[END_REF] of this type determines all other matrices up to scale.

Let G be the graph with 9 vertices shown in Figure 7. It was stated in the main part of the paper that this graph is solvable (Example 6). We can argue this fact using the analysis of the four-cycle from the previous example. Indeed, if we assign the matrices I 4 , g (4,5) , g (5,6) , g [START_REF] Hartley | Computation of the quadrifocal tensor[END_REF][START_REF] Heyden | Tensorial properties of multiple view constraints[END_REF] as shown in the figure, then up to rescaling we have that g (4,5) = I 4 + c 5 v T 4 and g -1 (5,6) = I 4 + c 5 v T 6 , where v 4 and v 6 are each determined up to a scalar multiple (more precisely, 10 Moreover, we can write

where

Multiplying these two expressions together we obtain

which yields

This relation can only be satisfied if α = 1 and

Because the orthogonality conditions that defined v 4 , v 6 , v 8 , v 8 are all independent (since the pinholes are generic), ( 21) can be satisfied only if these vectors are all zero. From this we deduce that all the matrices g (i,j) must be the identity, and the graph G is solvable. ♦ 10 Note that the inverse of a matrix of the form I + cv T 1 is given by I + cv T 2 where v2 = -1 1+c T v 1 v1. In particular v2 is a scalar multiple of v1.