/^creative ^commor ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 16 (2019) 473-486 https://doi.org/10.26493/1855-3974.1477.1c7 (Also available at http://amc-journal.eu) Convertible subspaces that arise from different numberings of the vertices of a graph* Henrique F. da Cruz t, Ilda Inácio , Rogerio Serodio Universidade da Beira Interior, Centro de Matemática e Aplicagoes (CMA-UBI), Rua Marques d'Avila e Bolama, 6201-001, Covilha, Portugal Received 6 September 2017, accepted 3 January 2019, published online 28 February 2019 Abstract In this paper, we describe subspaces of generalized Hessenberg matrices where the determinant is convertible into the permanent by affixing ± signs. These subspaces can arise from different numberings of the vertices of a graph. With this numbering process, we obtain some well-known sequences of integers. For instance, in the case of a path of length n, we prove that the number of these subspaces is the (n + 1)th Fibonacci number. Keywords: Determinant, permanent, Hessenberg matrix. Math. Subj. Class.: 15A15, 05C05, 05C30 1 Introduction Let Mn(C) be the linear space of all n-square matrices over the complex field C, and let Sn be the symmetric group of degree n. For A = [a ij ] G Mn (C), the permanent function is defined as n per(A) = IK(0. aesni=1 In a very similar way, the determinant function is defined as n det(A) = ^ sgnMlIaia(i), aesn i= 1 * Research partially supported by the project UID/MAT/00212/2013. t Correspondent author. E-mail addresses: hcruz@ubi.pt (Henrique F. da Cruz), ilda@ubi.pt (Ilda Inacio), rserodio@ubi.pt (Rogerio Serodio) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 474 Ars Math. Contemp. 16 (2019) 445-463 where sgn is the sign function. The determinant is undoubtedly one of the most well-known functions in mathematics with applications in many areas. The permanent function is also a well-studied function, since it has many applications in combinatorics, but while the determinant can be easily computed, no efficient algorithm for computing the permanent is known. This difficulty leads to the idea of trying to compute it by using determinants. This idea dates back to 1913 in a work of Polya [6], and it has been under intensive investigation since then. Polya observed that the permanent of a 2 by 2 matrix A is equal to the determinant of the related matrix B = a ii a 12 a2i a22 aii —ai2 a21 a22 However, Szego [8] proved that if n > 3, then there is no way to generalize this formula, i.e., there is no uniform way of changing the signs of the entries of a matrix A e Mn (C) in order to obtain a matrix B satisfying det(B) = per(A). (1.1) Szego's result didn't put an end to this question. In fact, the possibility that the permanent can be converted into the determinant by affixing ± signs is a research topic that remains active until today (see [1, 2] or [5] for recent works on this subject). In 1969, Gibson [3] proved that the linear space of lower Hessenberg matrices is a convertible subspace. That is, it is possible to change in a uniform way the signs of the entries of a matrix A in this subspace in order to obtain a matrix B satisfying (1.1). More recently, C. Fonseca presented a new class of convertible subspaces. These subspaces are constructed using simple graphs as follows: Definition 1.1 ([2]). Given a simple graph G with n vertices, numbered by the integers in {1,..., n}, a G-lower Hessenberg matrix A = [aj] is an n-square matrix such that aj = 0 whenever i < j and {i,j} is not an edge of G. If, in addition, aj = 0 whenever i > j or {i, j} is an edge of G, then we say that A is a full G-lower Hessenberg matrix. Obviously, two numberings of the vertices of a graph are the same if the sets of edges are equal. C. Fonseca [2] proved that if G is a generalized double star (the tree resulting from joining the central vertices of two stars by a path) whose vertices are numbered in a natural way (consecutive integers from left to right), the linear space of these G-lower Hessenberg matrices is a convertible subspace. Let G be a simple graph with n vertices numbered with 1,..., n. We say that G is well-numbered if the linear space of all G-lower Hessenberg matrices that arise from this numbering of the vertices of G is convertible. As we will see in the third section, not all graphs admit a well-numbering of its vertices. The characterization of the connected graphs for which such a numbering exist is our first main result. Theorem 1.2. A connected graph G admits a well numbering of its vertices if and only if G is a caterpillar. H. F. da Cruz et al.: Convertible subspaces that arise from different numberings 475 Recall that a caterpillar is a tree in which all vertices are within distance 1 of a central path. The interior vertices of the path are called nodes. Every caterpillar results from a sequence of stars (R1, R2,..., Rt), such that the central vertex of R is linked to the central vertex of Rj_i, i = 2,..., t, by a single edge. If a caterpillar results from a sequence of stars with an equal number r of vertices, then we will denote this type of caterpillars by Ct[r], where t is the number of the stars involved. So, Ct[1] is a path with t vertices, and C1 [r] is a star with r vertices. Example 1.3. The caterpillar C3 [4] is shown in Figure 1(a). The caterpillar C4 [2] is shown in Figure 1(b). (a) C3[4] (b) C4[2] Figure 1: Two examples of caterpillars. Theorem 1.2 states that the vertices of a caterpillar G can be numbered in a way such that the subspace of all G-lower Hessenberg matrices arising from that numbering is convertible. A natural question is to know if all numberings of the vertices of a caterpillar produce a convertible subspace. The answer is negative, and a simple example can be provided with a path. Let G be a path with n vertices. If the vertices of G are numbered in a natural way (consecutive integers from left to right), then from Definition 1.1, we obtain the linear space of classical lower Hessenberg matrices, which Gibson [3] proved to be a convertible subspace. However, if we enumerate the vertices of G in a different way, the subspace of all G-lower Hessenberg matrices arising from that numbering of the vertices of G may no longer be convertible. Example 1.4. Consider the path of length four numbered as in Figure 2. 14 2 3 Figure 2: A numbered path on 4 vertices. The subspace of the C4[1] -lower Hessenberg matrices with maximal dimension constructed from this numbered path is the subspace {/a11 0 0 «21 «22 «23 a31 032 033 \041 «42 043 which is not convertible as we will see in the next section. Thus, it is pertinent to ask how many different convertible subspaces, with maximal dimension, arise from different numberings of the vertices of a caterpillar. We restrict our study to caterpillars of the form Ct [r]. The answer is given in the next theorem which is our second main result: «14 «24 0 «44 € C, ij = 1,..., 4 « 476 Ars Math. Contemp. 16(2019)445-463 Theorem 1.5. Let r be a fixed integer, and G = Ct[r]. Assume that G has at least three vertices. The number of different convertible subspaces, with maximal dimension, that arise from the different numberings of the vertices of G is the (t + 1)th term of the sequence '0, if n = 0; 1, if n = 1; jan-1 + an-2, if n > 2. Example 1.6. In this example, we apply Theorem 1.5 to some caterpillars. Below each representation of the caterpillar (in Figures 3, 4 and 5), we give the number of convertible subspaces of G-lower Hessenberg matrices, with maximal dimension, that arise from different numberings of the vertices of that caterpillar. As we are going to see some of the sequences are well known. 1. For a path with three, four and five vertices see Figure 3. (a) 3 (b) 5 (c) 8 Figure 3: The number of convertible subspaces arising from Ct [1] for t = 3,4, 5. In general, the number of convertible subspaces arising from Ct[1], t > 3 is the (t + 1)th term of the OEIS [7] sequence A0 0 0 04 5, the sequence of the Fibonacci numbers. 2. If G = Ct [2], then for t = 2, 3,4 see Figure 4. (a) 5 (b) 12 (c) 29 Figure 4: The number of convertible subspaces arising from Ct [2] for t = 2, 3,4. In general, the number of convertible subspaces arising from Ct[2], t > 2 is the (t + 1)th term of the OEIS sequence A000129, the sequence of the Pell numbers, also known as lambda numbers. 3. If G = Ct [3], then for t = 1, 2,3,4 see Figure 5. (a) 3 (b) 10 (c) 33 (d) 109 Figure 5: The number of convertible subspaces arising from Ct[3] for t = 1, 2,3,4. H. F. da Cruz et al.: Convertible subspaces that arise from different numberings 477 In general, the number of convertible subspaces arising from Ct[3], t > 1, is the (t + 1)th term of the OEIS sequence A006190. This paper is organized as follows. In the next section, we present a simple criterium to decide when a subspace of G-lower Hessenberg matrices with maximum dimension is convertible. As we are going to see the convertibility of such subspace can be decided from the convertibility of a matrix of zeros and ones. In the third section, we prove our first main result, and describe how vertices numbering should be in order G be well-numbered. The characterization of such numberings allows proving Theorem 1.5. 2 Preliminary results An n-square (0,1)-matrix is a square matrix whose entries are just zeros and ones. Similarly, for an n-square (-1,1)-matrix. Let S = [sij] be an n-square (0,1)-matrix. For each i e {1,..., n} let n n ri = ^2 si,k, and c = ^ sfcji. k=1 k=1 The sequence R = (r1,... ,rn) is the row-sum sequence of S and the sequence C = (c1,..., cn) is the column-sum sequence of S. Definition 2.1. Two matrices A and B are permutation equivalent, if there exist permutation matrices P and Q of suitable sizes such that B = PAQ. An n-square (0,1)-matrix S defines a coordinate subspace Mn(S) = {S*X : X e Mn(C)}, where * denotes the Hadamard product. We say that Mn(S) is convertible if there exists an n-square (-1,1)-matrix C, such that det(C*X) = per(X), for all X e Mn(S). Let Tn = [ti,j] be an n-square (0,1)-matrix such that ti,j =0 if and only if i < j + 1. The coordinate subspace Mn (Tn) is the subspace of the lower Hessenberg matrices. Gibson [3] proved that if C = [ci j] is the n-square (-1,1)-matrix such that cijj = —1 if and only if j = i +1, then det(C*X) = per(X), for all X e Mn(Tn). Another important result due to Gibson states the maximum number of nonzero entries in a convertible matrix. 478 Ars Math. Contemp. 16 (2019) 445-463 Theorem 2.2 ([4]). Let A = [aj] be an n-square (0,1)-matrix such that per(A) > 0, and the permanent of A can be converted into a determinant by affixing ± signs to the elements of A. Then A has at most Q„ = i (n2 + 3n — 2) positive entries, with equality if and only if A is permutation equivalent to Tn. Observe that the row- and column-sum sequences of Tn are, respectively, R =(2, 3,..., n — 1, n, n) and C = (n,n,n — 1,,..., 3, 2). So, Theorem 2.2 gives a simple criterium to decide when an n-square (0,1)-matrix S, with Qn nonzero entries satisfying per(S) > 0 is convertible. Proposition 2.3. Let S be an n-square (0,1)-matrix with Qn nonzero entries satisfying per(S) > 0. Then S is convertible if and only if S is permutation equivalent to a (0,1)-matrix whose row-sum sequence is R = (2,3,..., n — 1, n, n), and the column-sum sequence is C = (n, n, n — 1,. .., 3, 2). Proof. The Hessenberg matrix Tn has row- and column-sum sequences R = (2, 3, ..., n — 1, n, n) and C = (n, n, n — 1,..., 3,2), respectively. By hypothesis, and by transitivity, S is permutation equivalent to Tn. Hence, by Theorem 2.2, S is convertible. If S is convertible, then S is permutation equivalent to Tn, and Tn has row-sum sequence R = (2, 3,..., n — 1, n, n), and column-sum sequence C = (n, n, n — 1, ..., 3, 2). □ Example 2.4. Consider the following matrices Si 110 0 0 110 10 11111 11111 11111 and S2 0 10 0 110 0 1110 1111 1111 Then, Si is not convertible because the row sum sequence of (2,3, 5, 5,5), but S2 is convertible because we can reorder the rows and the columns S2 in order to obtain a matrix whose row-sum sequence and column-sum sequence are (2,3,4, 5, 5) and (5,5,4,3, 2), respectively. The next result states that the convertibility of a coordinate subspace Mn(S) can be decided by the convertibility of S. Proposition 2.5. Let S be an n-square (0,1)-matrix with Q„ nonzero entries, and per(S) > 0. Then, Mn(S) is a convertible subspace if and only if S is convertible. Proof. If Mn(S) is a convertible subspace, then S is convertible. Assume that S is convertible. Then, there exists an n-square ( — 1,1)-matrix C such that det(C*S) = per(S). H. F. da Cruz et al.: Convertible subspaces that arise from different numberings . 479 Let S'n be the set of permutations a e Sn such that "=1 siCT(j) = 0. Since per(S) > 0, S'n = 0. We have n det(C*S) = Y sgn(a)nc^(i)Sia(i) CTesn ¿=1 nn = Y sgn(a) II ffesn ¿=1 ¿=1 where we conclude that sgn(a) n=1 ciCT(i) = 1 for all a e S'n. For any matrix A e Mn(S), we have n det(C * A) = Y sgn(a) JJ ctGS; i=1 nn = Yj sgn(a) JJ CiCT(i) JJ aiCT(i) i=1 i=1 n = yi ik« i=1 = per(A), hence, A is convertible. Since A is arbitrary, we conclude that Mn(S) is a convertible subspace. □ Let A = [aij] be an n-square matrix. We denote by A(i; j) the (n - 1)-square submatrix obtained from A after removing the ith row and the j,th column. Generalizing, A(i1;..., ik; j1,..., jk) denotes the square submatrix of A after removing the rows i1,... ,ik and the columns j1;..., jk. Gibson proved the following result. Lemma 2.6 ([3]). Let S = [sj] be a convertible matrix. If srs = 1, then S(r; s) is also convertible. A subspace version of this Lemma is as follows. Proposition 2.7. If Mn(S) is a convertible subspace, and sij = 1, then Mn-1(S(i; j)) is also a convertible subspace. Proof. It follows easy from Lemma 2.6, and Proposition 2.5. □ Corollary 2.8. If Mn(S) is a convertible subspace and sil,jl,..., sifc,jfc are k nonzero elements of S, then Mn-k (S(i1;..., ik; j1;..., jk)) is also a convertible subspace. Proof. Trivial by induction. □ 480 Ars Math. Contemp. 16 (2019) 445-463 3 Proofs of the main results We start this section with a result that comes easily from Proposition 2.5. Proposition 3.1. A connected graph G is well-numbered if and only if the correspondent full G-lower Hessenberg matrix of 0's and 1 's is convertible. Let Ln be the anti-identity matrix of order n. This matrix has in position (i, j) the element 1, if i + j = n +1, and 0 otherwise. Let A be an n-square matrix. We denote by Aat the matrix Aai := LnAtLn, where A1 is the transpose of A. The matrix Aai is the anti-transpose of A. Remark 3.2. Let A = [«j ] be an n-square matrix, and let Aat = [«a^t]. Then 1. aj = an-j+i,n-i+i, for all i, j = 1,..., n; 2. (Aat)at = A. The next result allows simplifying some of the proofs. Lemma 3.3. Let G be a graph with n vertices. If G is well-numbered, then G is also well-numbered replacing vertex i by vertex n — i +1, for all i = 1,..., n. Proof. Let G be a well-numbered graph with n vertices, and let S be the correspondent full G-lower Hessenberg matrix of 0's and 1's. Since G is well-numbered, by Proposition 2.3, S is permutation equivalent to a matrix whose row sum sequence is R = (2, 3,..., n — 1, n, n), and the column sum sequence is C = (n, n, n — 1,..., 3,2). By definition Sat is also permutation equivalent to a matrix whose row and column sum sequences are equal to R and C respectively, and for all i, j G {1,..., n} such that i > j, saj = 1. Consider the new enumeration of the vertices of G where the vertex i is replaced by n — i + 1 , for all i = 1,..., n, and let S' = [s^] be the correspondent full G-lower Hessenberg matrix of 0's and 1's. Let i, j G {1,... ,n} such that i < j, and i is adjacent to j in the initial enumeration of the vertices of G. Since n — j + 1 j we conclude, by Theorem 2.2, that S has exact nonzero entries, n — 1 of them above the main diagonal. By Definition 1.1 we conclude that G is a connected graph with n vertices and n — 1 edges, that is G is a tree. However, not all trees can be well-numbered. Proof of Theorem 1.2. By Proposition 2.5 we only have to consider (0,1)-matrices. Suppose G is a caterpillar with numbering as shown in Figure 6. We will prove by induction on the number of nodes that such numbering produces a convertible full G-lower Hessenberg matrix. If we have only one node (see Figure 7) the correspondent full G-lower Hessenberg H. F. da Cruz et al.: Convertible subspaces that arise from different numberings . 481 + ¿2 E fc-i E ¿i +1 •i - 1 ¿1 + 1 ¿1 + ¿2 - 1 Figure 6: Numbering of the caterpillar G. n- 1 1 n - 1 Figure 7: Special case with only one node. matrix is Li 1 0 0 . .0 0 1 1 1 0 . .0 0 1 1 1 1. .0 0 1 1 1 1. .1 0 1 1 1 1. .1 1 1 1 1 1. .1 1 1 This matrix is convertible by Proposition 2.3. Let's suppose that the enumeration is valid for caterpillars with k — 1 nodes, and that A is the correspondent full G-lower Hessenberg matrix. For a caterpillar with k nodes (see Figure 8) the correspondent full G-lower Hessenberg matrix is 2 n 2 n A 0 S = 0 ... 0 1 1 Lk where 1 is a matrix whose entries are all 1's, the line above Lk corresponds to the edge between the last two nodes, and Lk is the full G-lower Hessenberg matrix arising from the last node and has structure as L1. By induction hypothesis A is convertible. Thus, by Proposition 2.3, A is permutation equivalent to a matrix with row- and column-sum sequence ^2, 3,..., Xi—1 1 . It is straightforward to see that S is permutation equivalent to a matrix with row- and column-sum sequence ^2,3,..., Xi=1 2i=1 . Hence, there exists at least one enumeration for the caterpillars that produces a convertible full G-lower Hessenberg matrix. 482 Ars Math. Contemp. 16 (2019) 445-463 k-2 E U + 1 h ti + Î2 t1 - 1 ti + 1 + Î2 - 1 k-1 E t-i + 1 1 Figure 8: A caterpillar with k nodes. 2 We will prove by contradiction. Every tree that is not a caterpillar has at least one node connected with three other nodes. Therefore every tree which is not a caterpillar contains the graph in Figure 9 as vi V2 V3 V4 V5 V6 (I V7 Figure 9: The subgraph of a tree which is not a caterpillar. an induced subgraph. Let G be this graph and S be the full G-lower Hessenberg matrix of zeros and ones arising from an enumeration of the vertices of G. By Corollary 2.8, it is enough to prove that G cannot be well enumerated, that is, for every numbering of the vertices of G the rows or the columns of the correspondent full G-lower Hessenberg matrix of zeros and ones cannot be reordered to obtain (2, 3,4,5, 6, 7, 7). By Proposition 3.3, we only have to consider the numberings where v3 € {1, 2,3,4}. If v3 = 1, then no row of S sums two. If v3 = 2, then the first row of S is the only one that the sum equals two. Thus, the vertex numbered with 1 must be a terminal and the second row of S sums 5. To be convertible, the third row of S is the only one whose sum equals three. So, we have the subgraph in Figure 10. Therefore, no row of S has four ones. V3 2 3 *1 Figure 10: The subgraph in case of v3 = 2. If v3 = 3, then to have row-sums equal to two and three, and two column-sums equal to seven, vertices numbered with 1 and 2 must be adjacent. Similarly, to have two row-sums equal to seven vertices numbered with 6 and 7 are adjacent. Thus, no row has four ones. If v3 = 4, then vertices numbered with 1 and 2 cannot be simultaneously adjacent to v3 (otherwise, no row of S has two ones). The vertices numbered with 1 and 2 must be adjacent otherwise S doesn't have two column-sums equal to seven. By Lemma 3.3, vertices numbered with 6 and 7 must also be adjacent. Hence, if a row sums to four then no column can sum to four, and vice-versa. □ H. F. da Cruz et al.: Convertible subspaces that arise from different numberings . 483 Definition 3.4. Let T be a tree, and let R be a star with central vertex x. We say that R is a pendant star of T if: 1. R is an induced subgraph of T; 2. If we remove all the vertices of R, then we obtain a tree denoted by T/R; 3. x is adjacent to a single vertex of T/R. Remark 3.5. Note that every caterpillar with at least one edge has exactly two pendant stars. For proving Theorem 1.5, some lemmas are needed: Lemma 3.6. Let G = Ct[r] with n = tr vertices. If G is well-numbered, then the vertices numbered with 1, 2,..., r — 1, must be in the same pendant star, and the vertices numbered with n, n — 1,..., n — r + 1 must be in the other pendant star. Proof. We only need to prove that the vertices of G numbered with 1, 2,..., r — 1, must be in the same pendant star, because by Lemma 3.3 we conclude that n, n — 1,...,n — r + 1 must be in the other pendant star. If G is well-numbered, then the correspondent full G-lower Hessenberg matrix S of 0's and 1's is convertible. Therefore S is permutation equivalent to a matrix whose row-sum sequence is R = (2, 3,..., n —1, n, n), and column-sum sequence is C = (n, n, n — 1,..., 3,2). An ¿th column of S has n 1's if and only if the vertices numbered with 1,..., i — 1 are adjacent to the vertex numbered with i. Since G = Ct[r], the maximum degree of a vertex in G is r +1, and then the two columns of S with n 1's must be in the first r + 2 columns. Taking into account that caterpillars are sequences of stars connected by central vertices, we start showing that the vertices numbered with 1,..., r — 1 must be one of these stars, that is, the induced subgraph of G = Ct [r] that is the one of the stars involved in the construction of G. After that, we prove that this star is a pendant one. Assume that the vertices numbered with 1,..., r — 1 are not in the same star. Denote by R the star containing 1, and let j be the least integer less that r not in R. Denote by R' the star containing j. Several cases are needed to consider. Case 1: If 1,..., j — 1, j are pendant vertices, then having in mind the previous discussion, there are no two columns of S with n 1's, which is a contradiction. Case 2: If l g {1,..., j — 1} is the central vertex, and j is a pendant vertex, then the £th column of S has n 1's. If 1 < i < l — 1, then the ith row sums i + 1, the Ith row sums at least l + (r — 1) — (l — 1) + 1 = r +1, and the ith row, l +1 < i < j — 1, sums i. Since j is a pendant vertex of R', we conclude that no row of S sums j, which is a contradiction. Case 3: If the vertices 1,..., j — 1 are pendant vertices, and j is the central vertex of R', then ith row sums to i + 1, for all 1 < i < j — 1, and the jth row sums j + (r — 1) + 1 or j + (r — 1) + 2. Since the only row that can sum j + 1 is the row j + 1, the vertex j + 1 must be a pendant one of R'. Hence, S does not have two columns with n 1's, which is a contradiction. Case 4: If l g {1,..., j — 1} is the central vertex of R, and j is the central vertex of R', then the ith row of S, 1 < i < l —1, sums i + 1, the lth row sums at least l+(r — 1) — (l—1) + 1 = r +1, and the ith row of S, l +1 < i < j — 1, sums i. Since j is a central vertex, no row of S sums j, which is a contradiction. 484 Ars Math. Contemp. 16 (2019) 445-463 We have proved that the vertices of G numbered with 1,..., r - 1 must be in the same star R. Now we will prove that R is pendant. Suppose that this is not the case. Let i, 1 < i < r - 1 be the central vertex of R. Then the ¿th row of S, 1 < i < i -1, sums i + 1, the i111 row sums i +(r -1) - (i -1) + 2 = r + 2, because R is not pendant, and the ith row, i +1 < i < j - 1, sums i. Since the ith row sums r + 2, the (r + 1)th row must sum r +1 and the rth row must sum r. Then the vertices r and r + 1 must be pendant vertices of R, which is a impossible. If 1,..., r -1 are pendant vertices of R, the central vertex of this star must be numbered with r, r + 1 or r + 2, otherwise there are no two columns of S with n 1's. • For r, since R is not pendant, there are no row of S with r +1 1's. • For r +1, the vertex r must be adjacent to r +1, otherwise there are no two columns of S with n 1's. Then r is the central vertex of another star. Then, the rth row of S sums at least r + (r - 1) + 1 = 2r, the (r + 1)th row sums at least r + 2. Then S does not have a row with r + 1 1's. • Finally, for r + 2, by a similar procedure, we conclude that there is no row of S with r + 1 1's. □ Lemma 3.7. Let G = Ct[r]. If G is well-numbered, then the vertices of one of the pendant stars R are numbered with 1 up to r +1. If r + 1 is a vertex of R, then r + 1 is central, and r is adjacent to r + 1. If r is a vertex of R, then the central vertex can be any i, 1 < i < r. Proof. In the previous Lemma, we proved that 1,..., r - 1 must lay all in a pendant star. We only have to prove that the remaining vertex must be numbered with r or r + 1. We have to consider two cases: Case 1: If the pendant vertices of R are numbered with 1,..., r -1, then the central vertex can only be numbered with r or r +1. Otherwise, S does not have two columns with n 1's. By the same reason, if r + 1 is central, then r must be adjacent. Case 2: If the central vertex of R is i, 1 < i < r - 1, then there remains a pendant vertex. Suppose that this pendant vertex is j > r + 1. In this case, the row r sums at least r + 1, and no row sums r. Hence, R is numbered with 1,..., r. If r is a vertex of R, and i, 1 < i < r, is the central vertex, then the correspondent full G-lower Hessenberg matrix of 0's and 1' s satisfies the condition of Proposition 2.3. □ Corollary 3.8. Let G = Ct[r]. If G is well-numbered, then the vertices of one of the pendant stars R are numbered with n = tr down to n - 1 - r. If n - 1 - r is a vertex of R, then n - r - 1 is central and n - r is adjacent to n - 1 - r. If n - r is a vertex of R, then the central vertex can be any i, n - r < i < n. Proof. It follows directly from Lemmas 3.3 and 3.7. □ We are now in condition to prove our second main result: Proof of Theorem 1.5. The proof is by induction on t, the number of stars in a caterpillar. If t = 1, then r > 3. By Lemma 3.7, the central vertex of G can be numbered with any i € {1,..., r}. So, the number of different convertible subspaces is a2 = r. If t = 2, then G has n = 2r, r > 2, vertices. By Lemma 3.7, each star has r different ways to be well numbered by consecutive numbers. Therefore, this gives r2 different H. F. da Cruz et al.: Convertible subspaces that arise from different numberings . 485 well numberings for G with each star having consecutive numbers. Besides these, by the same Lemma, it is possible to interchange vertices r and r + 1, giving another convertible subspace. So the total number of different convertible subspaces is a3 = r2 + 1. Let t > 2, and assume that the theorem holds for all j < t. Let G = Ct+1[r]. By hypothesis there are at+1 convertible subspaces that arise from the different numberings of the caterpillar Ct[r]. The caterpillar G is obtained from Ct[r] by augmenting with a star with r vertices. By induction hypothesis and Corollary 3.8, there are rat+1 convertible subspaces that arise from a numbering of G, where the vertices of the new pendant star are numbered consecutively with tr + 1,..., (t + 1)r. There are also convertible subspaces that arise from a numbering of G, where the central vertex of new pendant star is numbered with tr. By induction hypothesis, this number is at. Then the total number of convertible subspaces that arise from the different numberings of the vertices of G is rat+1 + at = at+2. □ As we already saw, the number of well numberings of the vertices of a path with t vertices is the (t + 1)th Fibonacci number. In Table 1, we present all well-numbered paths of lengths 3, 4, and 5. Table 1: All well-numbered paths with 3, 4, and 5 vertices. n = 3 1 2 3 2 1 3 132 n=4 12 3 4 12 4 3 2 13 4 2 14 3 13 2 4 n=5 1 2 3 4 5 2 3 4 5 1 3 2 4 5 1 2 4 3 5 2 4 3 5 1 3 2 5 4 1 2 3 5 4 2 3 5 4 References [1] M. P. Coelho and M. A. Duffner, Subspaces where an immanant is convertible into its conjugate, Linear Multilinear Algebra 48 (2001), 383-408, doi:10.1080/03081080108818681. [2] C. M. da Fonseca, An identity between the determinant and the permanent of Hessenberg-type matrices, Czechoslovak Math J. 61 (2011), 917-921, doi:10.1007/s10587-011-0059-1. [3] P. M. Gibson, An identity between permanents and determinants, Amer. Math. Monthly 76 (1969), 270-271, doi:10.2307/2316368. [4] P. M. Gibson, Conversion of the permanent into the determinant, Proc. Amer. Math. Soc. 27 (1971), 471-476, doi:10.2307/2036477. [5] A. Guterman, G. Dolinar and B. Kuzma, P6lya convertibility problem for symmetric matrices, Math. Notes 92 (2012), 624-635, doi:10.1134/s0001434612110053. 486 Ars Math. Contemp. 16(2019)473-486 [6] G. Pölya, Aufgabe 424, Arch. Math. Phys. Ser. 3 20 (1913), 271. [7] N. J. A. Sloane (ed.), The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org. [8] G. Szego, Losung zu Aufgabe 424, Arch. Math. Phys. Ser. 3 21 (1913), 291-292.