ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 141-151 https://doi.org/10.26493/1855-3974.1517.e42
(Also available at http://amc-journal.eu)
Graph characterization of fully indecomposable nonconvertible (0,1)-matrices with minimal number of ones*
Mikhail Budrevich
Faculty of Algebra, Department of Mathematics and Mechanics, Moscow State University, Moscow, GSP-1, 119991, Russia, and Moscow Institute of Physics and Technology, Dolgoprudny, 141701, Russia
Alexander Guterman
Faculty of Algebra, Department of Mathematics and Mechanics, Moscow State University, Moscow, GSP-1, 119991, Russia, and Moscow Institute of Physics and Technology, Dolgoprudny, 141701, Russia
Bojan Kuzma
University ofPrimorska, Glagoljaska 8, SI-6000 Koper, Slovenia, and IMFM, Jadranska ulica 19, SI-1000, Ljubljana, Slovenia
Received 27 October 2017, accepted 15 July 2019, published online 10 September 2019
Let A be a (0,1)-matrix such that PA is indecomposable for every permutation matrix P and there are 2n + 3 positive entries in A. Assume that A is also nonconvertible in a sense that no change of signs of matrix entries, satisfies the condition that the permanent of A equals to the determinant of the changed matrix.
We characterized all matrices with the above properties in terms of bipartite graphs. Here 2n + 3 is known to be the smallest integer for which nonconvertible fully indecomposable matrices do exist. So, our result provides the complete characterization of extremal matrices in this class.
* The work of the second and the fourth authors was partially supported by Slovenian Research Agency (research core fundings No. P1-0288, No. P1-0222, and by grant BI-RU/16-18-033). The work of the first and the third authors is supported by Russian Scientific Foundation grant 17-11-01124.
The authors are especially thankful to the referee for communicated to them the gap which existed in Remark 3.15 of the original draft.
Gregor Dolinar
University of Ljubljana, Faculty of Electrical Engineering,
Tržaška cesta 25, SI-1000, Ljubljana, Slovenia, and IMFM, Jadranska ulica 19, SI-1000, Ljubljana, Slovenia
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
142
ArsMath. Contemp. 17 (2019) 141-151
Keywords: Permanent, indecomposable matrices, graphs. Math. Subj. Class.: 05C40, 15A27, 15A04, 05C50
1 Introduction
Let Mm,n (E) denote the set of matrices of size m x n with entries from a certain algebraic set E. Unless explicitly stated otherwise, E C Z is a subset of integers. Typically E = {0,1} or E = {-1,1} and in these two cases we will write Mm,n(0,1) or Mm,n(±1), and if m = n, then we write shortly Mn,n(E) = Mn(E). We consider two well known functions of matrices, permanent and determinant, which are defined by formulas:
n	n
per A = ^ \\(Ha{i), det A = II sSn(a)ai^(i),
aesni=1	aesni=1
where Sn is the group of permutations of order n and sgn(a) is a sign of permutation a.
Permanent is a good counting function in combinatorics and applications, but there is no fast algorithms known for computing the permanent function itself on arbitrary matrices. Ryser formula which requires O(n2n-1) multiplication operations is still one of the best known algorithms, for details see [1] or [9]. Moreover, Valiant proved that computing even a permanent of (0,1)-matrix is #P-complete problem ([12]). Recent investigations of permanents of (0,1) and (-1,1) matrices can be found in [6] and [3], correspondingly, and references therein. In comparison, the determinant which is very similar to permanent can be easily computed by Gauss elimination algorithm. One of the possible approaches to compute permanent is to convert it by a certain transformation to the determinant. The sign-conversion is one of the classical possibilities to construct such a transformation.
We say that matrix A G Mn(0,1) is sign convertible or just convertible if there is matrix X G Mn(±1) such that per A = det(A o X), where operation o is the Hadamard, i.e., entrywise product. The notion of convertibility was presented by Polya in [10] and studied by different mathematicians (for details see [4, 5, 9]). Convertibility of (0,1)-matrices is equivalent to many problems in graph theory (for details see [7, 8, 11, 13]). Thus the class of (0,1)-matrices is particularly important.
In [4] different notions of bounds of convertibility were presented. We say that integer Qn is an upper bound for convertibility if for any A G Mn(0,1) with per A > 0 and with more than Qn nonzero entries it follows that A is not convertible. We say that wn is a lower bound for convertibility if any matrix A G Mn(0,1) with less than wn positive entries is convertible. It is known that Qn = n	(see [5]) and wn = n + 6 (see [4]).
In [2] lower bounds for convertibility were found under additional assumption that matrices are indecomposable or fully indecomposable. Note that instead of indecomposable some authors use other terminology like irreducible, see a book by Brualdi and Ryser [1]. Since the present paper is a continuation of our previous work [2] we use the same terminology as in [2]. Notice that the term "fully indecomposable" is also used in the same monograph (see [1, page 112]). Let us state the corresponding definitions below.
E-mail addresses: mbudrevich@yandex.ru (Mikhail Budrevich), gregor.dolinar@fe.uni-lj.si (Gregor Dolinar), guterman@list.ru (Alexander Guterman), bojan.kuzma@famnit.upr.si (Bojan Kuzma)
M. Budrevich et al.: Graph characterization of fully indecomposable nonconvertible ... 
143
Definition 1.1. A matrix A e Mn (0,1) is called decomposable if there exists permutation matrix P e Mn(0,1) such that
where B, D are square matrices and C is possibly a rectangular matrix. If A is not decomposable, it is called indecomposable.
Definition 1.2. A matrix A e Mn(0,1) is called partially decomposable if there exist permutation matrices P,Q e Mn (0,1) such that
where B, D are square matrices and C is possibly a rectangular matrix. If A is not partially decomposable, it is called fully indecomposable.
Remark 1.3. One observes easily that A e Mn(0,1) is not fully indecomposable if and only if for some integer p e {1,..., n — 1} there exists a zero block of size p x (n — p) in A.
Remark 1.4. We note that a fully indecomposable matrix is always indecomposable, but the converse may not be true. Observe that in each row and in each column of a fully indecomposable matrix there are at least 2 positive entries.
In [2, Example 4.3] we showed that lower bound for indecomposable matrices equals n + 6 and can not be improved. For fully indecomposable matrices better lower bound was found in the same paper.
Theorem 1.5 ([2]). Let A e Mn(0,1) be a fully indecomposable matrix with less than 2n + 3 positive entries. Then matrix A is convertible.
Our aim is to describe extremal case of Theorem 1.5. Namely, we classify all fully indecomposable matrices with 2n + 3 positive entries which are nonconvertible. Our paper is organized as follows. In Section 2 we reformulate the notion of convolution (introduced in [2]) in terms of bipartite graphs and describe the properties of this operation. In Section 3 we prove our main result Theorem 3.13 on the characterization of the extremal case using the language of the graph theory.
2 Convolution via bipartite graphs
The following notion of convolution was presented in [2].
Definition 2.1. Let A e Mn(0,1) and let the first row of A has exactly two non-zero entries aii, ai2. Then the convolution of A by the firstrow is the following matrix Si(A) e
Mn-i(0,1),
Si (A)
/max(a2i, a22) a23 max(a3i,a32) a33
\max(ani, an2) an3
ann
144
ArsMath. Contemp. 17 (2019) 141-151
Here we delete the first row and take the maximum between the corresponding elements in the first and second columns.
Similarly, if the i-th row of A has exactly two nonzero entries aij, aik, j < k, the convolution Si(A) G Mn-1(0,1) of A by the i-th row is defined as the matrix obtained from A by deleting the i-th row and k-th column and exchanging the j-th column by the maximum of j-th and k-th columns.
Notation 2.2. Let A G Mm,„(S), a C {1,..., m} and £ C {1,..., n}. By A(a|£) we denote the matrix obtained from A by removing rows with indexes from a and columns with indexes from £. By A[a|£] we denote the submatrix of A located on intersection of rows with indexes from a and columns with indexes from £. We will write shortly A( 11,2) instead of A({}|{1,2}) etc.
Our main goal in this section is to present the notion of convolution with the help of graphs. Let r = r(V, W, E) be a simple bipartite graph with V U W as the set of vertices and E as the set of edges. Write V = {v1,..., vm} and W = {w1,..., wn}. We say that matrix A G Mm,n(0,1) is biadjacency matrix of r if the following holds: aij = 1 if and only if {vi, wj } G E. Thus |V | is equal to the number of rows in A and |W | is equal to the number of columns in A. The number of edges of a vertex v is a valency of this vertex. Since we study square (0,1)-matrices we will consider only bipartite graphs with |V | = |W |.
Remark 2.3. Let r = r(V, W, E) be a simple bipartite graph and A g M„(0,1) its biadjacency matrix. Then permutation of rows of A corresponds to renumbering of vertices in V, permutation of columns of A corresponds to renumbering of vertices in W and transposition of A corresponds to exchange of sets V and W. Thus these transformations do not change the structure of the graph.
Suppose that convolution can be applied to a matrix A g Mn(0,1), i.e., suppose A has a row with exactly two nonzero entries. By Remark 2.3 we can assume that A has two positive elements a11 and a12 in the first row and S1(A) is a convolution of A by the first row. Let A be biadjacency matrix of r = r(V, W, E), see Figure 1(a), and S1(A) be biadjacency matrix of r1, see Figure 1(b).
V2	V3	V4
«►•v.	• •
I / ..•••■"
i / ,-•"
I ^ ..-•■' ..........
w2
(b) the result of convolution
w1 w2
(a) the original graph
Figure 1: Convolution.
M. Budrevich et al.: Graph characterization of fully indecomposable nonconvertible ... 145
Lemma 2.4. Let A e Mn(0,1). Let the first row of A has exactly two non-zero entries an,ai2, and let Si (A) be the convolution of A. Then bipartite graph r with biadja-cency matrix Si(A) is constructed from bipartite graph r with biadjacency matrix A by the following steps:
(1)	Vertices vi and wi are removed.
(2)	Every edge in r of the form {x, wi} for x e {v2,..., vn} is replaced by an edge in
ri of the form {x, w2} .
Proof. To obtain Si (A) from A the following transformations are done.
1.	The first row and the first column of A are removed. Thus vertices vi e V and
wi e W are removed from r.
2.	Since A(1|1,2) = Si(A)(|1) the corresponding subgraphs in r and ri coincide.
3.	In Si(A) elements of the first column are represented by max(aii,ai2), where i =
2.....	n. Since we consider (0,1)-matrices there are four possible options.
3.1.	Suppose aii = ai2 = 0. Then max(aii, ai2) = 0 and no edges in r and ri correspond to these entries of A and Si (A).
3.2.	Suppose aii = 1 and ai2 = 0. Then there is an edge {vi,wi} in r. Since max(aii, ai2) = 1 this edge in ri is replaced by {vi, w2}. For i = 2 this case is represented in Figure 1(a) for r and in Figure 1(b) for ri by dash-dotted edges.
3.3.	Suppose aii = 0 and ai2 = 1. Then there is an edge {vi,w2} in r. Since max(aii, ai2) = 1 this edge remains also in ri. For i = 4 this case is represented in Figure 1(a) for r and in Figure 1(b) for ri by dotted edges.
3.4.	Suppose aii = ai2 = 1. Then there are edges {vi,wi} and {vi,w2} in r. Since max(aii, ai2) = 1 these edges are replaced by the edge {vi, w2} in ri. For i = 3 this case is represented in Figure 1(a) for r and in Figure 1(b) for ri by dashed edges. In this case we will say that edges are merged.	□
3 Main result
We will use the following results obtained in [2].
Theorem 3.1 ([2, Theorem 3.6]). Let A e Mn(0,1). Let the first row of A have exactly two nonzero entries aii and ai2, and let Si(A) be the convolution of A. Then A is convertible if and only if Si(A) is convertible.
Theorem 3.2 ([2, Theorem 3.8]). Let A e Mn(0,1) be a fully indecomposable matrix with at most 2n + 2 positive entries. Then A is convertible.
Now we prove that the convolution of a fully indecomposable matrix is fully indecomposable.
Lemma 3.3. Let A e Mn (0,1). Let the first row of A have exactly two nonzero entries aii and ai2, and let Si(A) be the convolution of A. Let A be fully indecomposable. Then Si(A) is fully indecomposable.
146
ArsMath. Contemp. 17 (2019) 141-151
Proof. Assume on the contrary that Si (A) is partially decomposable. Then there exists a k x (n - k — 1) zero submatrix B = S1(A)[i1,..., i^j^, ..., jn_k_1] for some 1 < k < n — 2 and some i1 < • • • < ik and j < • • • < jn_k_1. We consider two cases depending on whether B includes the first column of S1 (A) or not.
1.	Suppose j > 1. Since A(1|1,2) = S1(A)(|1) then B is a submatrix of A as well, i.e., B = A[i1 + 1,...,ik + 1|j + 1,..., jn_k_1 + 1]. Since a1j; =0 for l > 2 and since j + 1 > 2 it follows that A[1, i1 + 1,..., ik + 1|j1 + 1,..., jn_k_1 + 1] is a (k + 1) x (n — k — 1) zero submatrix. So A is partially decomposable, a contradiction.
2.	Suppose j = 1. Let S1(A) = (sj). Since 0 = siij1 = max(aii+1j1, aii + 1j2) for any l = 1,..., k it follows that A[i1 + 1,..., ik + 111, j 1 + 1,..., jn_k_1 + 1] is a k x (n — k) zero submatrix. So A is partially decomposable, a contradiction. □
The following example shows that the converse does not hold, i.e., if S1(A) is fully indecomposable, then A is not necessarily a fully indecomposable.
Example 3.4. The matrix A, defined below, is partially decomposable while S1 ( A) is fully indecomposable.
/1 1 0 0\ 0 111 0 111 0111
A=
Notation 3.5. Let A g Mn(0,1). By v(A) we denote the number of positive entries of A. By Jk g Mk (0,1) we denote the k-by-k matrix with all entries equal to 1.
Lemma 3.6. Let A g Mn (0,1), n > 3, be a fully indecomposable nonconvertible matrix with v(A) = 2n + 3. Then the convolution can be applied recursively to obtain J3. On step k of the process we obtain fully indecomposable, nonconvertible matrix of order (n — k) with 2(n — k) + 3 positive entries.
Proof. By Remark 1.4 in each row of A there are at least two positive elements. Since v(A) = 2n + 3 by Pigeonhole principle there is a row in A with exactly 2 positive entries. With no loss of generality these entries are a11 and a12. Since the convolution S1 removes the first row of A it follows that v(S1(A)) < 2(n — 1) + 3. By Theorem 3.1, S1(A) is nonconvertible and by Lemma 3.3, S1(A) is fully indecomposable. Thus by Theorem 3.2, v(S1(A)) > 2(n — 1) + 3.
Combining both inequalities we obtain v(S1(A)) = 2(n — 1) + 3 and matrix S1 (A)
meets all the conditions of this lemma. Repeating the arguments n — 3 times we obtain J3.
□
Lemma 3.7. Let A g Mn (0,1), n > 3, be a fully indecomposable nonconvertible matrix with v(A) = 2n + 3 and with exactly two positive entries a11 = a12 = 1 in the first row. Let A and S1(A) be the biadjacency matrices of bipartite graphs r and r1, respectively. Then r1 is constructed from r without merging edges.
Proof. Suppose the edges {x, w1} and {x, w2} of r are merged by convolution. It means that there is i > 1 such that ai1 = ai2 = 1. These two positive entries are replaced by one in matrix S1(A). Thus v(S1 (A)) < 2n + 3 — 3 = 2(n — 1) + 2, which contradicts Lemma 3.6.	□
M. Budrevich et al.: Graph characterization of fully indecomposable nonconvertible ... 
147
Lemma 3.8. Let A e Mn(0,1), n > 3, be a fully indecomposable nonconvertible matrix with v(A) = 2n + 3. Then in A there are n — 3 columns (rows) with exactly two positive entries and 3 columns (rows) with exactly three positive entries.
Proof. By Remark 1.4 in each row of A there are at least two positive entries. By Lemma 3.6 we can construct sequence of n — 3 convolutions to obtain matrix J3. By Lemma 3.7 there are no merges of edges, hence after applying a convolution the number of positive entries in non-deleted rows does not change.
To prove the statement for columns we transpose the matrix and repeat our arguments.
□
A chain of three edges is any sequence of edges of the form {a, vi}, {vi, v2}, {v2, b} which constitute a path of length 3 for some vertices a, v1, v2, b.
Lemma 3.9. Let A e Mn(0,1), n > 3, be a fully indecomposable nonconvertible matrix with v (A) = 2n + 3 and with exactly two positive entries a11 = a12 = 1 in the first row. Then the first or the second column (or both) contains exactly two nonzero entries. Moreover, suppose the first column of A contains exactly two nonzero entries and let A and S1(A) be the biadjacency matrices of bipartite graphs r and r1, respectively. Then r1 is obtained from r by replacing a chain of three edges by a single edge and deleting the two intermediate vertices of this chain.
Remark 3.10. No generality is lost in assuming that first column contains exactly two nonzero entries — we can always swap the first two columns to achieve this.
Remark 3.11. Conversely, under the assumptions and notations of Lemma 3.9, r is obtained from r1 by subdividing an edge with two additional vertices. Note that this procedure preserves bipartiteness of graphs.
Proof of Lemma 3.9. By Lemma 3.8 in each column of A there are either 2 or 3 positive entries. Since permutation of columns does not change the structure of the graph we consider three cases.
1.	Suppose that in the first and in the second columns of A there are three positive entries. By Lemma 3.7 no edges were merged in S1(A). Thus there are four positive entries in the first column of S1(A). Note that by Lemma 3.6, S1(A) is fully indecomposable nonconvertible matrix of order n — 1 and v(S1(A)) = 2(n — 1) + 3, so by Lemma 3.8 in each column of S1 (A) there are at most three positive entries, a contradiction.
2.	Suppose there are two and three positive entries in the first and in the second column of the matrix. With no loss of generality we can permute columns of the matrix to obtain two positive entries in the first column and three positive entries in the second column. By Lemma 3.7 no edges are merged thus ai1ai2 = 0 for any i > 2. We may assume that a11 = a21 = 1 in the first column and a12 = a32 = a42 = 1 in the second column. The structure of the graph is represented in Figure 2(a). By Lemma 2.4 convolution S1(A) remove vertices v1 and w1 and edges {v1, w1} and {v1, w2} and the edge {v2, w1} is replaced by the edge {v2, w2}. The resulted graph is represented in Figure 2(b). The removed elements of r are represented by dotted edges (Figure 2(a)) the added element of r1 are represented by dashed edge (Figure 2(b)). Thus the chain {w2, v1}, {v1, w1}, {w1, v2} is replaced by the edge {w2, v2} to obtain graph r1. The lemma is proved in this case.
148	ArsMath. Contemp. 17 (2019) 141-151
vi
V2
V3
V4
wi	W2
(a) the chain before convolution is marked by the dotted edges
V2
V3
V4
W2
(b) the same chain after convolution is the dashed edge
Figure 2: Convolution of matrix with 3 positive entries in 1st column and 2 positive entries in 2nd column.
3. Suppose there are two positive entries in the first column and two positive entries in the second column. By Lemma 3.7 no edges are merged thus ailai2 = 0 for any i > 2. We may assume that all = a2l = 1 in the first column and al2 = a32 = 1 in the second column. The structure of the graph is represented in Figure 3(a). By Lemma 2.4 convolution S1(A) remove vertices v1 and wl and edges {v1, wl} and { v1 , w2} and the edge { v2 , wl} is replaced by the edge {v2 , w2}. The resulted graph is represented in Figure 3(b). Thus the chain {w2, vl}, {vl, wl}, {wl, v2} (dotted edges, Figure 3(a)) is replaced by the edge {w2, v2} (dashed edge, Figure 3(b)) to obtain graph rl. The lemma is proved.	□
vi
wi w2 (a) the chain before convolution is marked by the dotted edges
(b) the same chain after convolution is the dashed edge
Figure 3: Convolution of matrix with 2 positive entries in 1st column and 2 positive entries in 2nd column.
Lemma 3.12. Let r be a graph obtained from the bipartite graph rl by subdividing one or more its edges with even number of points. Let A(rl) and A(r) be the corresponding biadjancency matrices. If A(rl) is fully indecomposable then same holds for A(r).
Proof. We use the notation from the proof of Remark 3.11. It suffices, by induction, to consider the case when r is obtained from rl by subdividing only one of its edges with two
M. Budrevich et al.: Graph characterization of fully indecomposable nonconvertible ... 
149
vertices. Without loss of generality we may assume that the subdivided edge is [v\, w\] and that we are adding vertices v0, w0. Then, the matrix corresponding to r has the form
vo	vi	V2 ..	. Vn
1	1	0 ..	.0
1	0	* ..	.*
0	*	* ..	.*
wo wi
A(r)= w2
0 ★ ★ ... ★
where * denote the entries of the biadjacency matrix A(^). It follows from Remark 1.3 that A(r) is fully indecomposable if and only if it does not contain a zero block of size p x (n +1 — p) for some p = 1,..., n where n +1 is the size of A(r). Now, by the induction, the n x n matrix A(^) is fully indecomposable so it does not contain a zero block of size 1 x (n — 1). It follows that the (n +1) x (n +1) matrix A(r) has at least two ones in each row, i.e. has no zero block of size 1 x n. The first row of A(r) contains n — 1 zeros. However, at the corresponding columns (2)-(n +1) (the starting column being indexed by 0), the other rows of A(r) consists of elements of A(r1) so cannot have n — 1 zero entries. That is, A(r) does not contain a zero block of size 2 x (n — 1). Likewise we see that inside columns (3)-(n) the matrix A(r1) does not contain a zero 2 x (n — 2) which implies that A(r) contains no 3 x (n — 2) block. Proceed inductively to deduce that A(r) contains no zero p x (n +1 — p) block. Hence, A(r) is fully indecomposable. □
Theorem 3.13. Let A e Mn(0,1), n > 3, be a fully indecomposable nonconvertible matrix with v(A) = 2n + 3. Let r = r(V, W, E) be a simple bipartite graph with A as its biadjacency matrix. Then up to renumbering of vertices, r has the following three properties.
(1)	Vertices vj, wj, where i, j e {1, 2,3}, have valency 3, and every other vertex has valency 2.
(2)	If i, j e {1,2,3} and {vj, wj} e E, then there is a unique path connecting vj to wj whose intermediate vertices are all ofvalency 2.
(3)	The graph is connected.
Remark 3.14. The disjoint union of a complete bipartite graph and an even cycle K3 3 + C*2„-6 satisfies all the assumptions of Theorem 3.13 except the third item. This graph is not a biadjacency graph of fully indecomposable n-by-n matrix with 2n + 3 units.
Proof. By Lemma 3.6 there is a sequence of n — 3 convolutions to obtain matrix J3 from A. Matrix J3 is a biadjacency matrix of a complete bipartite graph K3,3. This graph fulfills the conditions of the theorem. Let us reverse these convolutions to obtain graph r. Note that by Remark 3.11 on each reverse step the resulted graph is bipartite.
By Lemma 3.9 each convolution replaces a chain of three edges by a single edge. Thus the reverse operation will add two vertices with valency 2 and replace a single edge by a chain of three edges, hence the valencies of vertices which were added on the previous steps do not change. Thus Condition (1) of the theorem is satisfied after each reverse operation.
All edges in the graph K3,3 can be represented as a chain of length 1 from vertex vj to vertex wj. Thus each reverse operation replaces a single edge by a chain of three
150
ArsMath. Contemp. 17 (2019) 141-151
edges whose both intermediate vertices are of valency 2 in some chain of edges. Obviously this operation preserves chains of edges from v to wj, where i, j e {1, 2,3}, possibly extending a length of one of these chains by 2. Thus Conditions (2) and (3) are satisfied.
Remark 3.15. With the help of Remark 3.11 and Lemma 3.12 we can formulate Theorem 3.13 also in the following way. A bipartite graph r corresponds to a fully indecomposable nonconvertible biadjacency matrix A with v(A) = 2n + 3 if and only if r is obtained from K3 3 by subdividing each edge with an even number of vertices (possibly 0).
Recall that if two matrices are the same modulo permutations of rows/columns and transposition, then their biadjacency graphs are isomorphic. Conversely, assume the biadjacency graphs r and r2 of two fully indecomposable nonconvertible n-by-n matrices Ai, A2 € Mn(0,1) with 2n + 3 units are isomorphic. The two graphs are bipartite having two maximum sets of independent vertices V and Wj. Their graph isomorphism must either map V1 bijectively onto V2 and W1 bijectively onto W2, or it maps V1 bijectively onto W2 and W1 bijectively onto V2. The first case corresponds to permuting rows/columns of matrix A1 to obtain A2, while the second case composes this with transposition.
Therefore, the cardinality of the set Q of equivalent classes of fully indecomposable nonconvertible matrices A € Mn (0,1) with v (A) = 2n + 3, modulo permutations of rows, columns, and transposition, equals the number of pairwise nonisomorphic graphs, obtained from K3 3 by subdividing each edge with an even number of vertices (possibly 0) such that in total we place additional 2(n - 3) vertices.
Theorem 3.16. Up to a permutation of rows and columns and up to a transposition, any fully indecomposable nonconvertible matrix A € Mn(0,1) with v(A) = 2n + 3 can be described by a matrix C € M3(Z+), such that the sum of elements of C is n — 3.
Proof. In the proof of Theorem 3.13 it is was shown that any bipartite graph r with a fully indecomposable nonconvertible biadjacency matrix A € Mn(0,1), v(A) = 2n + 3, can be constructed by a sequence of n — 3 replacements of a single edge by a chain of three edges. Thus for a full description of r we must define lengths of chains from vj to wj, where i, j € {1, 2,3}. Each chain has length 2k + 1, where k > 0 is a number of times when an edge from this chain was replaced by a chain of three edges. Equivalently, it is a number of convolutions that modified this chain. By Lemma 3.6 total number of convolutions to obtain K33 from r is n — 3. It follows that r can be described by 9 numbers kj, i € {1,..., 9}, such that J2i=1 kj = n — 3.
Let us arrange these numbers in a matrix C = (cjj) € M3(Z+) such that cjj is equal to a number of convolutions corresponding to a chain from vj to wj. Permutation of rows (columns) is equivalent to renumbering of vertices vj, i € {1,2,3} (wj, i € {1,2,3}). Transposition of C is equivalent to a permutation of sets of vertices V and W of a graph r. Thus the structure of r does not change and the theorem is proved.	□
Example 3.17. For n = 7 there are 16 not equivalent nonconvertible (0,1)-matrices with 2n + 3 ones. They are described by the following nonnegative integer matrices with the sum of elements equal to 4.
□

4 0 0 0 0 0 0 0 0
3 1 0 000 000
300 010 000
220 000 000
M. Budrevich et al.: Graph characterization of fully indecomposable nonconvertible ... 
151
'2 0 0\ /2 1 1\ 2 1 0\ /2 1 0201 [000] [001] 1010 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 2 0 0 2 0 0 1 1 1 100] [011] [010] [100 0 0 0 0 0 0 0 0 1 0 0 0
1 1 0 1 1 0 1 1 0 1 1 0 011 ] [110] [010 ] [001 0 0 0 0 0 0 0 0 1 0 0 1
References
[1]	R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, volume 39 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1991, doi:10.1017/ cbo9781107325708.
[2]	M. Budrevich, G. Dolinar, A. Guterman and B. Kuzma, Lower bounds for Poiya's problem on permanent, Internat. J. Algebra Comput. 26 (2016), 1237-1255, doi:10.1142/ s0218196716500521.
[3]	M. V. Budrevich and A. E. Guterman, Krauter conjecture on permanents is true, J. Comb. Theory Ser. A 162 (2019), 306-343, doi:10.1016/j.jcta.2018.11.009.
[4]	G. Dolinar, A. E. Guterman and B. Kuzma, On the Gibson barrier for the Polya problem, Fundam. Prikl. Mat. 16 (2010), 73-86, doi:10.1007/s10958-012-0912-2.
[5]	P. M. Gibson, Conversion of the permanent into the determinant, Proc. Amer. Math. Soc. 27 (1971), 471-476, doi:10.2307/2036477.
[6]	A. E. Guterman and K. A. Taranin, On the values of the permanent of (0,1)-matrices, Linear Algebra Appl. 552 (2018), 256-276, doi:10.1016/j.laa.2018.04.026.
[7]	C. H. C. Little, A characterization of convertible (0,1)-matrices, J. Comb. Theory Ser. B 18 (1975), 187-208, doi:10.1016/0095-8956(75)90048-9.
[8]	W. McCuaig, Polya's permanent problem, Electron. J. Combin. 11 (2004), #R79 (83 pages), https://www.combinatorics.org/ojs/index.php/eljc/article/ view/v11i1r79.
[9]	H. Minc, Permanents, volume 6 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1984, doi:10.1017/cbo9781107340688.
[10]	G. Polya, Aufgabe 424, Arch. Math. Phys. Ser. 3 20 (1913), 271.
[11]	N. Robertson, P. D. Seymour and R. Thomas, Permanents, Pfaffian orientations, and even directed circuits, Ann. of Math. 150 (1999), 929-975, doi:10.2307/121059.
[12]	L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), 189-201, doi:10.1016/0304-3975(79)90044-6.
[13]	V. V. Vazirani and M. Yannakakis, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, in: U. Peled (ed.), Combinatorics and Complexity, Elsevier, Amsterdam, pp. 179-190, 1989, doi:10.1016/0166-218x(89)90053-x, papers from the conference held at the University of Illinois at Chicago, Chicago, Illinois, June 15 - 17, 1987.