---
abstract: 'One of possible interpretations of the well-known König–Hall–Egerváry theorem is a full characterization of all bipartite graphs extremal for fractional matchings of a given weight (or, equivalently, a characterization of $(0,1)$-matrices extremal for partial fractional diagonals of a given length). In this paper we initiate the study of $d$-partite $d$-uniform hypergraphs that are extremal for fractional perfect matchings (or, equivalently, $d$-dimensional $(0,1)$-matrices that are extremal for polydiagonals). For this purpose, we analyze similarities and differences between $2$-dimensional and multidimensional cases and put forward a series of questions and conjectures on properties of multidimensional extremal matrices (extremal hypergraphs). We also prove these conjectures for several parameters and provide a number of supporting constructions and examples.'
author:
- 'A. A. Taranenko[^1]'
date: 'November 25, 2018'
title: 'On the König–Hall–Egerváry theorem for multidimensional matrices and multipartite hypergraphs'
---

\[section\] \[teorema\][Lemma]{} \[teorema\][Proposition]{} \[teorema\][Property]{} \[teorema\][Corollary]{} \[teorema\][Conjecture]{} \[teorema\][Remark]{} \[teorema\][Construction]{} \[teorema\][Question]{} \[teorema\][Problem]{}

Introduction {#introduction .unnumbered}
============

The König–Hall–Egerváry theorem is one of the basic results in discrete mathematics.

Let $A$ be a $(0,1)$-matrix of order $n$. The minimum number of lines (rows and columns) sufficient for covering all unity entries of $A$ is equal to the maximum number of ones that do not share the same rows and columns.

or

A $(0,1)$-matrix $A$ of order $n$ contains a unity partial diagonal of length $l$ if and only if there are no $s \times t$ zero submatrices in $A$ for which $s+t = 2n - l + 1.$

or

For a bipartite graph, the minimum size of a vertex covering is equal to the maximum size of a matching.

A variety of proof strategies are known for the theorem. One of them (see, for example, book [@shrivbookcomb] by Schrijver) is based on linear programming, fractional matchings, and fractional vertex covers. Also the König–Hall–Egerváry theorem may be expressed as a complete characterization result of matrices (or graphs) extremal in some sense.

To illustrate this we define a *polyplex* $K$ of weight $W$ to be a nonnegative matrix in which the sum of entries over each row and each column is not greater than $1$ and the sum of all entries is equal to $W$. In other words, a polyplex of order $n$ and of weight $W$ is a fractional matching in a bipartite graph with parts of size $n$. We call a polyplex of the maximum possible weight (i.e. weight $n$) to be a *polydiagonal*.

We will say that a $(0,1)$-matrix $A$ is extremal for polyplexes of weight $W$ if on the support of $A$ there are no polyplexes of weight $W$ or greater but after changing any zero entry of $A$ to one the resulting matrix has a polyplex of weight at least $W$. Then one more equivalent form of the König–Hall–Egerváry theorem is the following: all $(0,1)$-matrices extremal for polyplexes of weight $W$ are exactly the matrices in which zero entries form an $s \times t$ submatrix with $s + t = 2n - \left\lceil W \right\rceil + 1$.

For multidimensional matrices we also introduce a polyplex that is equivalent to a fractional matching in a $d$-partite $d$-uniform hypergraph with parts of equal sizes. The main aim of this paper is, using geometry interpretation and theory of linear programming, to take several steps towards the generalization of König–Hall–Egerváry theorem for a multidimensional case and investigate multidimensional matrices extremal for polyplexes. In other words, we research $d$-partite $d$-uniform hypergraphs extremal for fractional matchings of a given weight.

There are a plenty of results on fractional matchings concerning sufficient conditions for a hypergraph to have a fractional matching of a given weight. Some of them look for the minimum degree for existence of perfect matchings. For example, with the help of geometric approach Keevash and Mycroft [@keevmyc] obtain asymptotic degree conditions for existence of perfect matchings that generalizes a number of other results for perfect matchings in hypergraphs. Moreover in this book it can be found a number of references on papers devoted to minimum degree problems for mathchings in hypergraphs. For the survey of results on these problems see also [@rodlsurv] by Rödl and Ruciński.

For a $d$-partite $d$-uniform hypergraph with parts of equal size, the degree condition sufficient for existence of a perfect matching was proved in [@aharonipartite]. The fractional matching polytope of a hypergraph is studied, for instance, in [@furedipoly]. At last, for recent progress on the connection between the number of edges and the matching number of a hypergraph see [@huang].

One more possible generalization of the König–Hall–Egerváry theorem is the following conjecture wrongly attributed to Ryser [@ryser] (for clarification see [@bestwan]): in a $d$-partite $d$-uniform hypergraph the size of the minimum vertex cover is not greater than the size of the maximum matching multiplied by $d-1$. The best progress is that this conjecture is true for $3$-partite hypergraphs proved by Aharoni [@aharoni], and extremal $3$-partite hypergraphs for this conjecture were described in [@haxellnarins]. Also for $d = 4$ and $d=5$ its approximate version was proved by Haxell and Scott [@haxellscott].

Finally, there are some generalizations of the Hall theorem of distinct representatives in literature. One of them for hypergraphs belongs to Aharoni and Haxell [@aharonihall], and a vector version of the Hall theorem for common transversals is proved by Woodall [@woodall].

Let us describe the structure of this paper. In Section 1 we define the main concepts including definitions on not only multidimensional polyplexes and extremal matrices but (fractional) hyperplane covers. When a polyplex corresponds to a fractional matching in a $d$-partite hypergraph, a hyperplane cover of a multidimensional matrix is exactly a fractional vertex cover of the same hypergraph.

In Section 2 we recall the duality between the problems on the maximum fractional matching and the minimum fractional vertex hyperplane cover in a hypergraph and state the same duality for polyplexes and hyperplane covers. Also we deduce some easy consequences of the linear programming theory applied to polyplexes and hyperplane covers.

In Section 3 we probe our approach on the case of $2$-dimensional matrices providing one of the proofs of the König–Hall–Egerváry theorem. We also find the differences between the $2$-dimensional and multidimensional cases and reveal some properties of $2$-dimensional extremal matrices. In the second part of this section we formulate the programme for researching multidimensional extremal matrices, raise the main questions of this paper and propose a number conjectures. In particular, one of these conjectures is equivalent to that every $d$-partite hypergraph extremal for a fractional perfect matching is extremal for an integer perfect matching too. If we succeed in completing of the above programme, we obtain a characterization of extremal matrices for polyplexes that is equivalent to the multidimensional König–Hall–Egerváry theorem.

Following our research programme, in Section 4 we consider the question on the equivalence between extremal matrices and their optimal hyperplane covers and in Section 5 we provide some properties of optimal hyperplane covers of extremal matrices. A series of constructions of extremal matrices is given in Section 6, and Section 7 is devoted to the property of diagonal extremality of extremal matrices. In Section 8 we look closer at extremal matrices of orders $2$ and $3$ and prove some additional properties for them. The paper concludes with a list of examples of extremal matrices of small orders and dimensions.

The main results of present consideration are the characterizations of all extremal matrices of big deficiencies and extremal matrices with two-value optimal hyperplane covers. In particular, all main conjectures from Section 3 are confirmed for such classes of extremal matrices.

Definitions
===========

A *$d$-dimensional matrix $A$ of order $n$* is an array $(a_\alpha)_{\alpha \in I^d_n}$, $a_\alpha \in\mathbb R$, with the set of indices $I_n^d= \left\{ (\alpha_1, \ldots , \alpha_d):\alpha_i \in \left\{1,\ldots,n \right\}\right\}$. A multidimensional matrix $A$ is called *nonnegative* if all entries of $A$ are nonnegative. A *$(0,1)$-matrix* is a multidimensional matrix whose all entries are equal to zero or one. The *support* $supp(A)$ of a nonnegative matrix $A$ is the set of indices $\alpha$ of all nonzero entries $a_\alpha$.

A *hyperplane* in a $d$-dimensional matrix $A$ is a $(d-1)$-dimensional submatrix of $A$ obtained by fixing one of coordinates. Denote by $\Gamma_{i,j}$ the $j$-th hyperplane by direction $i$ in the matrix $A$ (the $i$-th coordinate is assigned to be $j$). Given a $d$-dimensional matrix $A$ of order $n$, let $A_\alpha$ be the $d$-dimensional submatrix of order $n-1$ obtained by deleting all hyperplanes containing index $\alpha$.

Multidimensional matrices $A$ and $A'$ are said to be *equivalent* if one can be turned to the other by permutations of hyperplanes of one direction and by permutations of directions (matrix transpositions).

A *polyplex* $K$ of *weight* $W$ is a nonnegative multidimensional matrix in which the sum of entries over each hyperplane is not greater than 1 and the sum of all entries equals $W$. Note that the set of all polyplexes of the same weights is a convex polytope.

A polyplex of weight $n$ and order $n$ is said to be a *polydiagonal*. The simplest example of a polydiagonal is a *diagonal* that is a $(0,1)$-matrix with exactly one unity entry in each hyperplane.

Strictly speaking, it would be more correctly to use something like “partial fractional diagonal” instead of notion “polyplex” and “fractional diagonal” instead of “polydiagonal”. But we will use the present notations for the sake of brevity and convenience. Plexes are usually applied for latin squares and latin hypercubes in which they mean sets of entries evenly distributed among all hyperplanes and symbols of a latin hypercube. See survey [@wansurv] for results on plexes in latin squares and paper [@mymulti] for a generalization of plexes for multidimensional matrices.

We will say that a multidimensional $(0,1)$-matrix $A$ contains a polyplex $K$ if $supp (K)\subseteq supp(A) $. An *optimal* polyplex in a matrix $A$ is a polyplex of a maximum weight contained in the matrix $A$.

A *hyperplane cover* of a $d$-dimensional $(0,1)$-matrix $A$ of order $n$ is a nonnegative $(d \times n)$-table $\Lambda$ assigning nonnegative weights to all hyperplanes of $A$ in such a way so each unity entry of $A$ *is covered with weight* not less than 1, i.e. we demand that for each $\alpha$ from the support of $A$ it holds $\sum\limits_{\Gamma_{i,j} \ni \alpha}  \lambda_{i,j} \geq 1.$

The *weight* of a hyperplane cover $\Lambda$ is the sum of all its entries $\lambda_{i,j}$. It is not hard to see that the set of all hyperplane covers of a given weight is a convex polytope.

We call a hyperplane cover $\Lambda$ of a matrix $A$ *optimal* if it has a minimum weight among all hyperplane covers of $A$. Note that every matrix $A$ of order $n$ has a hyperplane cover of weight $n$ because we can always cover the support of the matrix $A$ by $n$ hyperplanes of one direction having weight 1, so the weight of the optimal hyperplane cover of any matrix of order $n$ is not greater than $n$.

Given a nonnegative table $\Lambda$, we define a $(0,1)$-matrix $A(\Lambda)$ such that the support of $\Lambda$ consists of only those entries that covered with weight at least $1$ by $\Lambda$. Also for a given index $\alpha$ let us denote by $\Lambda_\alpha$ the $d \times (n-1)$-table obtained from $\Lambda$ by deleting weights of all hyperplanes containing the index $\alpha$.

For every hyperplane cover $\Lambda$ the matrix $A(\Lambda)$ is equivalent to some *stepped* matrix $B$ such that for all $j_1$ and $j_2$ inequality $j_1 \leq j_2$ implies that the hyperplane $\Gamma_{i,j_1}$ of direction $i$ is not greater than the hyperplane $ \Gamma_{i,j_2}$ of the same direction entrywise. On the other hand, not for every stepped matrix $B$ there is a hyperplane cover $\Lambda$ such that $B = A(\Lambda)$. Multidimensional stepped matrices of order $2$ are known as monotonic boolean functions, and $2$-dimensional stepped matrices are $(0,1)$-matrices in echelon form.

A $d$-dimensional $(0,1)$-matrix $A$ of order $n$ is called *extremal* if $A$ has no polydiagonals and after replacing each zero entry by unity one the resulting matrix has a polydiagonal. The *deficiency* $\delta$ of an extremal matrix $A$ of order $n$ is the difference between $n$ and the weight of the optimal polyplex in $A$.

At last we introduce a special class of extremal matrices. We will say that a multidimensional $(0,1)$-matrix $A$ is *diagonally extremal* if it has no polydiagonals and for each index $\alpha$ such that $a_\alpha = 0$ the submatrix $A_{\alpha}$ has a diagonal.

Linear programming approach
===========================

The problem on the maximum weight of a polyplex $K$ in a given $d$-dimensional $(0,1)$-matrix $A$ of order $n$ can be stated as the following linear programming problem: $$\begin{gathered}
 \label{maxplexpr}
\sum\limits_{\alpha} k_\alpha \rightarrow \max; \notag\\
\sum \limits_{\alpha \in \Gamma_{i,j}}  k_{\alpha} \leq 1 \mbox{ for all } i = 1, \ldots, d, ~ j = 1, \ldots, n; \\
k_{\alpha} \geq 0  \mbox{ for all } \alpha \in supp (A); ~~~ k_{\alpha} = 0  \mbox{ for all } \alpha \not\in supp (A).
\notag\end{gathered}$$

Since all constraints use only integers, each multidimensional $(0,1)$-matrix has an optimal polyplex with rational entries. Because there exists a polynomial algorithm depending on the number of variables and on the size the constraint parameters to solve a linear programming problem, we have that an optimal polyplex in any multidimensional matrix can be found in polynomial time.

For a given $d$-dimensional $(0,1)$-matrix $A$ of order $n$, a problem on an optimal hyperplane cover $\Lambda$ looks as follows: $$\begin{gathered}
 \label{mincoverpr}
\sum\limits_{i=1}^d \sum\limits_{j=1}^n \lambda_{i,j} \rightarrow \min; \notag\\
\sum \limits_{\Gamma_{i,j} \ni \alpha}  \lambda_{i,j} \geq 1 \mbox{ for all } \alpha \in supp (A); \\
\lambda_{i,j} \geq 0 \mbox{ for all } i = 1, \ldots, d, ~ j = 1, \ldots, n.
\notag\end{gathered}$$ Similarly to polyplexes, for each multidimensional matrix $A$ there exists an optimal hyperplane cover $\Lambda$ having all rational entries and if the matrix is given then its optimal hyperplane cover can be found in polynomial time.

Problem (1) is equivalent to the problem on the maximum weight of a fractional perfect matching in a $d$-partite $d$-uniform hypergraph with parts of equal sizes, and the problem (2) aims for a vertex cover of a minimum weight in such hypergraphs. The constraint matrices $U$ and $U^{T}$ for both problems are submatrices of the vertex-hyperedge incidence matrix of the complete $d$-partite $d$-uniform hypergraph with parts of size $n$.

As for fractional matchings and fractional vertex covers in general hypergraphs, we have the following.

\[multikonig\] Given a $d$-dimensional $(0,1)$-matrix $A$ of order $n$, the maximum weight of a polyplex in $A$ is equal to the minimum weight of its hyperplane cover.

The problem (2) is the dual problem to the problem (1). The duality theorem for linear programming implies that the optimal value for the objective function of the problem (1) coincides with the optimal value in the problem (2).

We finish this section with one more easy corollary of the linear programming.

\[slackuse\] Assume that $A$ is a $d$-dimensional $(0,1)$-matrix of order $n$, $\Lambda$ is its optimal hyperplane cover, and $K$ is an optimal polyplex in $A$.

1.  If entry $k_{\alpha}$ is nonzero then index $\alpha$ is covered with weight $1$ by $\Lambda$; if some index $\alpha$ is covered by $\Lambda$ with not unity weight then $k_\alpha = 0$ for all optimal polyplexes in $A$.

2.  If $\lambda_{i,j} > 0$ then the sum of entries of $K$ in the hyperplane $\Gamma_{i,j}$ equals $1$; if in a hyperplane $\Gamma_{i,j}$ the sum of entries of $K$ is not equal to $1$ then $\lambda_{i,j} = 0$ for all optimal hyperplane covers of $A$.

By the complementary slackness theorem applied to problems (1) and (2), we have that for each optimal polyplex $K$ and for each optimal hyperplane cover $\Lambda$ it holds $$k_{\alpha} \left( 1 -\sum\limits_{i=1}^d \lambda_{i,\alpha_i} \right) = 0 \mbox{ for each index } \alpha \in supp(A),$$ and $$\lambda_{i,j} \left( 1- \sum\limits_{\alpha \in \Gamma_{i,j}} k_{\alpha}\right) = 0 \mbox{ for each hyperplane } \Gamma_{i,j}.$$ The theorem immediately follows from these equalities.

$2$-dimensional case, main questions and conjectures {#problemsection}
====================================================

We start this section with reminding one of the proofs of the König–Hall–Egerváry theorem. For this purpose we need one more definition.

A rectangular integer matrix is called *totally unimodular* if the determinant of each square submatrix is equal to $0$ or $\pm 1$.

The proof of the following proposition can be found in book [@shrivbooklin].

\[unimod\] Let $Q$ be a rectangular $(0,1)$-matrix of size $n \times l$. Assume that the columns of $Q$ can be divided into two groups so that rows of the resulting submatrices contain no more than one unity entry. Then the matrix $Q$ is totally unimodular.

We are ready now to provide the proof of one of the equivalent forms of the König–Hall–Egerváry theorem.

\[2dimkonig\] Given a $2$-dimensional $(0,1)$-matrix $A$ of order $n$, the maximum length of a positive partial diagonal in $A$ is equal to minimum number of lines sufficient for covering all unity entries.

Note that the problem on the maximum length of a positive partial diagonal in $A$ is the integer version of problem (1). Similarly, the problem on the minimum number of lines covering all unity entries of $A$ is the integer variant of problem (2).

In the $2$-dimensional case the constraint matrix $U$ for one of the problems is an incidence matrix of some bipartite graph. By Proposition \[unimod\], the matrix $U$ is totally unimodular. It is known (see, for example, book [@shrivbooklin]) that if $U$ is a totally unimodular matrix then for all integer vectors $b$ the polyhedron $\left\{x: Ux \geq b \right\}$ has only integer vertices. Therefore, both integer problems (1) and (2) have the same integer optimal value.

Let us consider $2$-dimensional extremal matrices in more details. Theorem \[2dimkonig\] means that all $2$-dimensional extremal matrices of order $n$ are exactly a $(0,1)$-matrices with $k$ rows and $n-k-1$ columns filled by $1$ and with all other entries equal zero. Also, from the proof of Theorem \[2dimkonig\] we have that any $2$-dimensional matrix $A$ has an integer optimal polyplex (i.e. a partial positive diagonal of the maximal length) and any optimal polyplex is a concave sum of partial positive diagonals. All $2$-dimensional extremal matrices have deficiency $\delta = 1$ because the weight of an optimal polyplex in them is equal to $n-1$.

The optimal hyperplane cover $\Lambda$ of a $2$-dimensional extremal matrix is unique and is a $(0,1)$-table with $2$ rows and $n$ columns such that one row of $\Lambda$ contains $k$ unity entries and the other row has $n-k-1$ ones.

It also can be checked that an entry of an extremal matrix is contained in some optimal polyplex if and only if it is covered by weight exactly $1$ in the optimal hyperplane cover $\Lambda$.

At last we note that if we replace any zero entry of a $2$-dimensional extremal matrix by a unity one then the resulting matrix has a diagonal. It means that every $2$-dimensional extremal matrix is diagonally extremal.

Multidimensional extremal matrices are much more complicated object than the $2$-dimensional case. Let us set up the principal questions studied in this paper.

Does there exist a $1$-to-$1$ correspondence between extremal multidimensional matrices and their optimal hyperplane covers?

We believe that the answer to this question is positive. We have no examples of extremal matrices at which this correspondence is failed and we prove it for some classes of extremal matrices. In Section 4 we consider this question in more details. On the base of the whole paper, we propose the following conjecture.

\[uniquecon\] Every extremal matrix has the unique optimal hyperplane cover.

What are the possible values of deficiencies $\delta$ of extremal matrices? Given $n$ and $d$, how small can the deficiency of a $d$-dimensional extremal matrix of order $n$ be?

It is easy to bound the deficiency of multidimensional extremal matrices between zero and one.

\[weightextr\] If $\delta$ is a deficiency of an extremal matrix $A$ then $0 < \delta \leq 1$.

Since $A$ has no polydiagonals, we have $\delta > 0$.

By the definition, if we replace some entry $a_\alpha =0$ of the matrix $A$ by a unity one then we obtain some matrix with a polydiagonal $K$. Since $k_\alpha \leq 1$, the weight of the polyplex $K$ constricted back to the matrix $A$ is not less than $n-1$. Therefore, the deficiency $\delta$ of $A$ is at most $1$.

As we noted before, optimal polyplexes in multidimensional matrices have rational weights, so the deficiency $\delta$ of any extremal matrix is some rational number $\nicefrac{p}{q}$. The denominator $q$ of $\delta$ is bound by modulo by the largest minor of the incidence matrix of a $d$-partite hypergraph, so it does not exceed $d^{nd}$.

Considered examples of extremal matrices and the results our investigation motivate us to propose the following.

\[defcon\] The deficiency $\delta$ of any extremal matrix is equal to $\nicefrac{1}{m}$ for some $m \in \mathbb{N}$.

\[charcoverquest\]

Can we describe and enumerate all optimal hyperplane covers of extremal matrices (and extremal matrices itself)?

In the next sections we provide some necessary conditions for a hyperplane cover to define an extremal matrix and propose several constructions of extremal matrices and their optimal hyperplane covers. Also we give a characterization of all extremal matrices of big deficiencies. Our research leads us to the following conjecture.

\[multicon\] If $\Lambda$ is an optimal hyperplane cover of an extremal matrix of deficiency $\delta$ then all entries $\lambda_{i,j}$ are integer multiples of $\delta$.

Since a convex linear combination of optimal hyperplane covers of some matrix is an optimal hyperplane cover, we note that Conjecture \[multicon\] implies Conjecture \[uniquecon\] and if for some extremal matrix Conjecture \[multicon\] is true then such matrix has a unique optimal hyperplane cover.

What are the properties of multidimensional extremal matrices?

We know that all $2$-dimensional matrices are diagonally extremal. We do not find examples of multidimensional extremal matrices that are not diagonally extremal and all our constructions preserve this property. So we propose the following.

\[diagextrcon\] Every multidimensional extremal matrix is diagonally extremal.

Note that in terms of hypergraphs this conjecture means that every $d$-partite $d$-uniform hypergraph with parts of equal sizes extremal for fractional perfect matchings is also extremal for integer perfect matchings.

Equivalence of extremal matrices and their optimal hyperplane covers
====================================================================

This section aims to set up a natural bijection between extremal matrices and their optimal hyperplane covers. First of all, let us prove that the support of any extremal matrix is exactly the set of indices covered with weight at $1$ by its optimal hyperplane covers.

\[extrcode\] If $\Lambda$ is an optimal hyperplane cover of an extremal matrix $A$ then $A= A(\Lambda)$.

By the definition of the optimal hyperplane cover, $A \subseteq A(\Lambda)$.

Assume that $A \neq A(\Lambda)$. Since $\Lambda$ is an optimal hyperplane of $A$, the weight of $\Lambda$ is less than $n$. It implies that $A(\Lambda)$ does not contain a polydiagonal that contradicts to the extremality of the matrix $A$.

As an immediate corollary of this theorem, we have that every extremal matrix is equivalent to some stepped matrix.

Let us turn to the problem of uniqueness of the optimal hyperplane cover for a given extremal matrix. In contrast to optimal hyperplane covers, we note that even $2$-dimensional extremal matrices may contain many different optimal polyplexes. Moreover, there is a plenty of non-extremal matrices $A$ having many optimal hyperplane covers. Our next aim is to provide sufficient conditions for the existence of the unique optimal hyperplane cover and state this uniqueness for several classes of extremal matrices.

By the definition, an optimal hyperplane cover of a matrix $A$ is unique if and only if the linear programming problem (\[mincoverpr\]) for the matrix $A$ has a unique optimal solution. The uniqueness of optimal solution in linear programming was studied in a number of papers but in our work we are guided by [@floudas] and [@manga].

It is well known that the dual linear programming problem has a unique optimal solution if there exists a nondegenerate optimal solution of the primal problem or, equivalently, the primal problem has an optimal solution at which the linear independence constraint qualification (LICQ) is fulfilled. In terms of optimal polyplexes and optimal hyperplane covers this condition has the following form.

\[optuniind\] Let $A$ be a multidimensional $(0,1)$-matrix and let $K$ be an optimal polyplex in $A$. For each hyperplane $\Gamma_{i,j}$ assign a $(0,1)$-vector $v_{i,j}$ of length $|supp(A)|$ such that $v_{i,j}(\alpha) = 1$ if and only if $\alpha \in \Gamma_{i,j} \cap supp(A)$. Suppose $V$ is the set of all vectors $v_{i,j}$ such that $\sum\limits_{\alpha \in \Gamma_{i,j} } k_{\alpha} =1$. If $V$ is the set of linearly independent vectors then the matrix $A$ has the unique optimal hyperplane cover.

Another sufficient condition of uniqueness of the optimal hyperplane cover is that every optimal hyperplane cover $\Lambda$ of a matrix $A$ covers with weight $1$ the same set of indices.

\[optuniexact\] Suppose that $\alpha$ is an arbitrary from the support of a $(0,1)$-matrix $A$ such that it does not belong to the support of any optimal polyplex in this matrix. If $\alpha$ is covered with weight greater than $1$ by any optimal hyperplane cover then $A$ has the unique optimal hyperplane cover.

To formulate an alternative version of this condition we introduce one more definition. Given a hyperplane cover $\Lambda$, we will say that $\alpha$ is an *upper index* for $\Lambda$ if $\alpha$ is covered with weight at least $1$ by $\Lambda$ and all indices $\beta$ for which all $\lambda_{i,\beta_i} \leq \lambda_{i,\alpha_i}$ and $\sum\limits_{i=1}^d \lambda_{i,\beta_i} \neq \sum\limits_{i=1}^d \lambda_{i,\alpha_i}$ are covered by $\Lambda$ with weight less than $1$.

\[optuniupper\] If an optimal hyperplane cover $\Lambda$ of a matrix $A$ covers all upper indices with weight $1$ then $\Lambda$ is the unique optimal hyperplane cover for this matrix.

Let us give the last sufficient condition on uniqueness of optimal hyperplane cover that is derived from [@manga].

\[optunismall\] A hyperplane cover $\Lambda$ is the unique optimal hyperplane cover of the matrix $A$ if it remains an optimal solution for the problem $(2)$ with objective function $\sum\limits_{i=1}^d \sum\limits_{j=1}^n (1 \pm \varepsilon_{i,j}) \lambda_{i,j}$ for all arbitrary but sufficiently small $\varepsilon_{i,j}$.

So we propose the following conjectures that imply the uniqueness of optimal hyperplane covers of extremal matrices.

\[equivalent to Conjecture \[uniquecon\]\] \[hypuniind\] Let $A$ be a multidimensional extremal matrix and let $K$ be an optimal polyplex in $A$. Then the set of $(0,1)$-vector $v_{i,j}$ such that $v_{i,j}(\alpha) = 1$ if and only if $\alpha \in \Gamma_{i,j} \cap supp(A)$ and $\sum\limits_{\alpha \in \Gamma_{i,j} } k_{\alpha} =1$ is linearly independent.

\[equivalent to Conjecture \[uniquecon\]\] \[hypuniexact\] Let $\Lambda$ be an optimal hyperplane cover of an extremal matrix $A$. If index $\alpha$ is covered with weight $1$ by $\Lambda$ then there exists an optimal polyplex in $A$ whose support contains $\alpha$.

We conclude this section with a list of cases when extremal matrices have unique optimal hyperplane covers. All proofs will be given in future sections.

\[supporting Conjecture \[uniquecon\]\] If $A$ is one of the following extremal matrices then it has the unique optimal hyperplane cover.

1.  $A$ is an extremal matrix of deficiency $1$, $\nicefrac{1}{2}$ and $\nicefrac{1}{3}$.

2.  $A$ has an optimal hyperplane cover $\Lambda$ with all entries $\lambda_{i,j} \in \{0, \lambda\}$ for some $\lambda$.

Conditions on optimal hyperplane covers of extremal matrices {#condsection}
============================================================

The main aim of this section is to reveal some necessary and sufficient conditions on hyperplane covers $\Lambda$ for the matrix $A(\Lambda)$ be an extremal matrix.

We start the section with conditions on hyperplane covers following from Theorem \[slackuse\] (or from the complementary slackness theorem).

\[zeroexistextr\] If $\Lambda$ is an optimal hyperplane cover of an extremal matrix $A$ then each row of $\Lambda$ contains at least one zero entry.

Since $A$ has no polydiagonals, for each direction $i$ there exists a hyperplane $\Gamma_{i,j}$ such that the sum of entries of some optimal polyplex over the hyperplane $\Gamma_{i,j}$ is less than $1$. Theorem \[slackuse\] implies that $\lambda_{i,j} = 0.$

\[weightone\] If $\Lambda$ is an optimal hyperplane cover of an extremal matrix $A$ with deficiency $\delta < 1$ then in each hyperplane $\Gamma_{i,j}$ there exists index $\alpha$ covered by $\Lambda$ with weight exactly $1$.

Since $\delta < 1$, every hyperplane $\Gamma_{i,j}$ of $A$ contains a positive entry $k_{\alpha}$ of some optimal polyplex $K$. By Theorem \[slackuse\], we have that index $\alpha$ is covered with weight $1$ by the hyperplane cover $\Lambda$.

Let us consider other necessary conditions on optimal hyperplane covers of extremal matrices. From the definitions we deduce that $\Lambda$ is an optimal hyperplane cover of $A(\Lambda)$ and $A(\Lambda)$ is an extremal matrix of order $n$ if and only if both of the following demands hold:

1.  the matrix $A(\Lambda)$ contains a polyplex of the same weight as $\Lambda$;

2.  there are no hyperplane covers $\Lambda'$ of weight less than $n$ such that $A(\Lambda) $ is contained in $A(\Lambda')$.

The first demand is equivalent to that a certain system of linear equations is solvable and has a nonnegative solution. Indeed, if $\Lambda$ is an optimal hyperplane cover of weight $W$ for an extremal matrix, then problem (\[maxplexpr\]) turns to be equivalent to the following system of equations: $$\begin{gathered}
\sum\limits_{\alpha \in \Gamma_{i,j}} k_{\alpha} = 1 \mbox{ for all } \lambda_{i,j} >0; \\
\sum\limits_{\alpha \in supp(A)} k_{\alpha} = W.\end{gathered}$$

So we put forward the following problem.

\[related to Question \[charcoverquest\]\] What conditions on the table $\Lambda$ guarantee that it defines a multidimensional matrix with the optimal polyplex of the same weight? In other words, for which nonnegative tables $\Lambda$ the above system has a nonnegative solution?

Let us now consider the second demand claiming that there are no hyperplane covers of weight smaller than the number of their columns defining a matrix with a bigger support. With the help of this demand, we derive several necessary conditions on optimal hyperplane covers of extremal matrices.

\[extrnescond\] If $\Lambda$ is an optimal hyperplane cover of an extremal matrix $A$ of deficiency $\delta$ then there are no indices $\alpha$ covered by $\Lambda$ with weight strictly between $1 - \delta$ and $1$.

Assume that $a_{\alpha} = 0$ and index $\alpha$ is covered by $\Lambda$ with weight $1 - \varepsilon$ for $0 < \varepsilon < \delta$. Consider the hyperplane cover $\Lambda'$ that coincides with $\Lambda$ in all entries except for $\lambda_{1, \alpha_1}' = \lambda_{1, \alpha_1} + \varepsilon$. The weight of $\Lambda'$ is less than $n$ and the matrix $A$ is strictly contained in $A(\Lambda')$ that contradicts to the extremality of $A$.

\[boundsinrow\] If $\Lambda$ is an optimal hyperplane cover of an extremal matrix $A$ of deficiency $\delta$ then the difference between two non-equal entries $\lambda_{i,j}$ and $\lambda_{i,l}$ from the same row of $\Lambda$ is not less than $\delta$.

For the sake of contradiction, assume that $\lambda_{i,j} = \lambda_{i,l} + \varepsilon$ with $0 < \varepsilon < \delta$. Since $A = A(\Lambda)$ and $\Lambda$ has a minimum weight among all hyperplane covers of $A$, the hyperplane $\Gamma_{i,l}$ is strictly contained in the hyperplane $\Gamma_{i,j}$.

Consider the hyperplane cover $\Lambda'$ that coincides with $\Lambda$ in all entries except for $\lambda_{i,l}' = \lambda_{i, l} + \varepsilon$. that is $A(\Lambda)$ differs from $A$ in that the hyperplane $\Gamma_{i,l}$ is replaced by the hyperplane $\Gamma_{i,j}$. The weight of $\Lambda'$ is less than $n$ and the matrix $A$ is strictly contained in $A(\Lambda')$ so we have a contradiction to the extremality of $A$.

\[edgebound\] If $\Lambda$ is an optimal hyperplane cover of an extremal matrix $A$ of deficiency $\delta$ then for every entry $\lambda_{i,j}$ not equal to zero or one we have $\delta \leq \lambda_{i,j} \leq 1 - \delta$.

By Proposition \[zeroexistextr\], each row $i$ of $\Lambda$ contains at least one zero entry, so by Proposition \[boundsinrow\] all nonzero $\lambda_{i,j}$ are not less than $\delta$. On the other hand, if there exists $\lambda_{i,j}$ such that $1 - \delta < \lambda_{i,j} < 1$ then, by Proposition \[zeroexistextr\], in the hyperplane $\Gamma_{i,j}$ there is an index $\alpha$ covered with zero weights by all other hyperplanes. So the index $\alpha$ is covered by $\Lambda$ with weight strictly between $1 - \delta$ and $1$, but by Proposition \[extrnescond\], it is not possible.

The last corollary of the second demand is that optimal hyperplane covers cannot have many entries that are greater than $\nicefrac{1}{2}$.

\[biglambdabound\] If $\Lambda$ is an optimal hyperplane cover of a multidimensional extremal matrix of order $n$ then the number of $\lambda_{i,j} > \nicefrac{1}{2}$ is less than $n$.

We will say that an entry $\lambda_{i,j}$ of the optimal hyperplane cover $\Lambda$ is big if it is greater than $\nicefrac{1}{2}$ and is small otherwise.

Assume that $\Lambda$ has at least $n$ big entries. For sufficiently small $\varepsilon > 0$, consider the table $\Lambda'$ constructed from $\Lambda$ by the following way: we reduce by $\varepsilon$ all big entries and increase by $\frac{\varepsilon}{d-1}$ all small entries.

Note that $\Lambda'$ is also a hyperplane cover of the matrix $A$. Indeed,

-   if some index was covered by $d$ small entries of $\Lambda$, then it is covered with a bigger weight by $\Lambda'$;

-   if some index was covered by one big entry and $d-1$ small entries of $\Lambda$, then in it is covered with the same weight by $\Lambda'$;

-   if some unity entry of $A$ was covered by at least two big entries of $\Lambda$, then for sufficiently small $\varepsilon$ it is covered with weight at least $1$ by $\Lambda'$.

By the construction, the weight of $\Lambda'$ is not greater than the weight of $\Lambda$. Weights of $\Lambda$ and $\Lambda'$ cannot be the same because the table $\Lambda'$ cannot be an optimal hyperplane cover of $A$ (by Proposition \[zeroexistextr\], any optimal hyperplane cover of an extremal matrix should contain zeroes). If $\Lambda'$ has a smaller weight than $\Lambda$ then we have a contradiction with the optimality of $\Lambda$. Obtained contradictions complete the proof.

Using these propositions, we prove that Conjectures \[defcon\] and \[multicon\] are true for extremal matrices of big deficiencies.

\[supporting Conjectures \[defcon\] and \[multicon\]\] \[bigdeltalambda\] Let $\Lambda$ be an optimal hyperplane cover of an extremal matrix with deficiency $\delta$.

1.  If $\delta = 1$ then all $\lambda_{i,j}  \in \{ 0,1\}$.

2.  There are no extremal matrices with deficiency $\nicefrac{1}{2} < \delta < 1$. If $\delta = \nicefrac{1}{2}$ then all $\lambda_{i,j}  \in \{ 0, \nicefrac{1}{2}, 1\}$.

3.  There are no extremal matrices with deficiency $\nicefrac{1}{3} < \delta < \nicefrac{1}{2}$. If $\delta = \nicefrac{1}{3}$ then all $\lambda_{i,j}  \in \{ 0, \nicefrac{1}{3}, \nicefrac{2}{3}, 1\}$.

Clauses 1 and 2 immediately follow from Proposition \[edgebound\].

Let us prove Clause 3. Suppose that $A$ is an extremal matrix of deficiency $\delta$ such that $\nicefrac{1}{3} \leq \delta < \nicefrac{1}{2}$ and let $\Lambda$ be an optimal hyperplane cover of the matrix $A$. Taking into account Theorem \[onereduction\] that will be proved later, we may assume that the table $\Lambda$ does not contain unity entries.

Let $\lambda = \lambda_{i,j}$ be some nonzero entry in the table $\Lambda$ that is less than $\nicefrac{1}{2}$. Such $\lambda_{i,j}$ exists because $\Lambda$ should contain entries different from $0, \nicefrac{1}{2}$ and $1$ and because Proposition \[weightone\] implies that if there is some entry of $\Lambda$ greater than $\nicefrac{1}{2}$ then there exists an entry less than $\nicefrac{1}{2}$. By Proposition \[edgebound\], $\lambda \geq \delta \geq \nicefrac{1}{3}$.

Assume that $\lambda > \nicefrac{1}{3}$. Then Propositions \[extrnescond\] and \[boundsinrow\] imply that all entries of $\Lambda$ less than $\nicefrac{1}{2}$ are located only within the $i$-th row of $\Lambda$ and that all such entries are equal to $\lambda$. Using Proposition \[extrnescond\] again, we deduce that all nonzero entries in other rows are also the same and equal to $1 - \lambda$ laying strictly between $\nicefrac{1}{2}$ and $\nicefrac{2}{3}$. So the $i$-th row of $\Lambda$ has no more than $n-1$ $\lambda$-entries and, by Proposition \[biglambdabound\], there are no more than $n-1$ $(1-\lambda)$-entries in all other rows. Then the weight of the hyperplane cover $\Lambda$ is not greater than $ n -1 < n - \delta$; a contradiction.

Therefore there are no extremal matrices whose deficiencies are strictly between $\nicefrac{1}{3}$ and $\nicefrac{1}{2}$ and for all optimal hyperplane covers $\Lambda$ of extremal matrices of deficiency $\nicefrac{1}{3}$ it holds $\lambda_{i,j} \in \{0, \nicefrac{1}{3}, \nicefrac{2}{3}, 1 \}$.

At last we note that, since Conjecture \[multicon\] implies Conjecture \[uniquecon\], extremal matrices with deficiencies $1$, $\nicefrac{1}{2}$ and $\nicefrac{1}{3}$ have unique optimal hyperplane covers.

Constructions of extremal matrices
==================================

In this section we consider several constructions of infinite series of extremal matrices. All these constructions support conjectures proposed in Section \[problemsection\].

Iterative constructions
-----------------------

We start with constructions of extremal matrices based on extremal matrices of a smaller size. The first construction allows us easily increase the dimension of extremal matrices or discard insignificant dimensions of extremal matrices with identical hyperplanes.

\[extrconstrdim\] Let $B$ be a $d$-dimensional $(0,1)$-matrix of order $n$ in which each hyperplane of some direction is the same $(d-1)$-dimensional matrix $A$. The matrix $B$ is an extremal matrix of deficiency $\delta$ if and only if the matrix $A$ is an extremal matrix of deficiency $\delta$.

Every polyplex in the matrix $A$ can be expanded to a polyplex of the same weight in the matrix $B$: it is sufficient to take $n$ hyperplanes of some direction in the matrix $A$ and place them diagonally in the matrix $B$. Conversely, for every polyplex in $B$ there is a polyplex of the same weight in $A$: an entry of a polyplex in $A$ is the sum of values of a polyplex in $B$ over all copies of this entry in the matrix $B$. Above correspondences work even when we change one of zero entries of $A$ or $B$ to a unity one. Therefore matrices $A$ and $B$ have polyplexes of the same weight and after replacing some of their zero entry to one they simultaneously have or do not have polydiagonals.

Next we describe a series of constructions of multidimensional matrices that allow us to obtain extremal matrices of a greater order from a given extremal matrix.

Let $\Lambda$ be an optimal hyperplane cover of a $d$-dimensional matrix $A$ of order $n$ and of deficiency $\delta$. On the base of table $\Lambda$ we construct the $d \times (n+1)$-tables $\Lambda'$ in three ways:

\[extrconstrorder\]

1.  For an index $\alpha$ of $A$ covered by $\Lambda$ with weight $1$, $\Lambda'$ is obtained from $\Lambda$ by attaching entries $\lambda_{i,\alpha_i}$ to the $i$-th row for all $i = 1, \ldots, d$.

2.  $\Lambda'$ is obtained by attaching a $1$-entry to one of rows of the table $\Lambda$ and attaching $0$-entries to other its rows.

3.  Assume that the $j$-th row of $\Lambda$ contains a $\delta$-entry. Then we construct a table $\Lambda'$ by attaching a $(1-\delta)$-entry to one of rows (some $i$-th row for $i \neq j$) of $\Lambda$, a $\delta$-entry to the $j$-th row and attaching $0$-entries to other rows.

\[extrconstrorderproof\] If $\Lambda$ is an optimal hyperplane cover of an extremal matrix $A$ of deficiency $\delta$ then tables $\Lambda'$ obtained from $\Lambda$ via Construction $\ref{extrconstrorder}$ are optimal hyperplane covers of the extremal matrices $B = A(\Lambda')$ of order $n+1$ and of deficiency $\delta$.

Denote by $\beta$ the index of the matrix $B$ belonging to the intersection of all new hyperplanes. In all three constructions the submatrix $B_\beta$ is exactly the matrix $A$ and entry $b_\beta$ in matrices $B$ equals one. Each matrix $B$ has no polydiagonals, because the weight of $\Lambda'$ is less than $n+1$. Moreover, matrices $B$ contain polyplexes of weight $n+1 - \delta$ that consist of some polyplex of weight $n-\delta$ in the matrix $A$ and $b_\beta =1$.

So to prove the theorem it remains to show that after replacing each zero entry $b_\gamma$ of the matrix $B$ by a unity entry we obtain a polydiagonal in the resulting matrix. If index $\gamma$ is taken from the submatrix $B_{\beta}$ then it holds because of the extremality of the matrix $A$.

Therefore, we may assume that indices $\gamma$ and $\beta$ share same hyperplanes in directions $i_1, \ldots, i_l$. Let us describe the construction of polydiagonals using index $\gamma$ for all three clauses of Construction \[extrconstrorder\].

1\. By the construction, $\alpha$ is some index of $A$ covered by $\Lambda$ with weight $1$ and $\Lambda'$ is obtained from $\Lambda$ by doubling entries corresponding to $\alpha$. Let $\sigma$ denote the index that coincides with $\beta$ in all positions except for $ \sigma_{i_j} = \alpha_{i_j}$ for all $j=1, \ldots, l$. The construction implies that submatrices $B_{\beta}$ and $B_{\sigma}$ coincide. So we have that the submatrix $B_{\sigma}$ is equal to $A$, index $\gamma $ belongs to $ B_{\sigma}$ and that $b_{\sigma} = 1$. Thus if we replace entry $b_\gamma$ by $1$ the resulting matrix will have a polydiagonal.

2\. By Proposition \[zeroexistextr\], there exist index $\alpha$ covered with weight $0$ by the hyperplane cover $\Lambda$. Next we repeat the proof of the previous clause with that index $\alpha$ instead the previous one.

3\. If index $\gamma$ does not belong to a new hyperplane of direction $i$ then we can follow proofs of the previous clauses. Otherwise, $\gamma$ is an index covered with weight $1 - \delta$ by a hyperplane of direction $i$ and with weight $0$ by hyperplanes of other directions. The submatrix $B_\gamma$ is defined by a hyperplane cover that differs from $\Lambda$ only in that there is a $\delta$-entry instead of some $0$-entry in its $j$-th row. Then the matrix $B_{\gamma}$ strictly contains the matrix $A$ and the extremality of the matrix $A$ implies that $B_{\gamma}$ has a polydiagonal.

Let us consider which of these three constructions can be reversed. Firstly, we note that in the first clause of Construction \[extrconstrorder\] it is not necessary to use an optimal hyperplane cover $\Lambda$ of some extremal matrix to obtain an optimal hyperplane cover $\Lambda'$ of another extremal matrix $B$.

Indeed, consider the following $3$-dimensional matrix of order $5$. $$B = \left( \begin{array}{ccccc|ccccc|ccccc|ccccc|ccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & \mathbb{1} & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 
\end{array} \right)$$ The optimal hyperplane cover of $B$ is $$\Lambda' = \frac{1}{5} \left(\begin{array}{ccccc} 4 & 2 & \mathbb{2} & 1 & 0 \\ 3 & 2 & \mathbb{2} & 1 & 0 \\ 3 & 2 & \mathbb{1} & 1 & 0 \end{array}\right).$$ The bold entry of the matrix $B$ is covered by the hyperplane cover $\Lambda'$ with weight $1$. Note that the table $\Lambda'$ can be constructed by attaching the bold column to the table $$\Lambda= \frac{1}{5} \left(\begin{array}{cccc} 4 & 2 & 1 & 0 \\ 3 & 2 & 1 & 0 \\ 3 & 2 & 1 & 0 \end{array}\right).$$ It can be checked that the matrix $A(\Lambda)$ is not extremal and is contained in the following $3$-dimensional extremal matrix of order $4$ with the optimal hyperplane cover $\Lambda''$: $$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right);
~~
\Lambda'' = \frac{1}{7} \left(\begin{array}{cccc} 5 & 3 & 1 & 0 \\ 4 & 3 & 2 & 0 \\ 4 & 3 & 2 & 0 \end{array}\right).$$

So the first clause of Construction \[extrconstrorder\] is not reversible. Also we would like to note that this matrix $B$ is an example of an extremal matrix such that it has an index $\alpha$ covered with weight $1$ by an optimal hyperplane cover but the submatrix $B_{\alpha}$ is not an extremal matrix.

Next we show that the second clause of Construction \[extrconstrorder\] can be completed to the equivalence between extremal matrices.

\[onereduction\] Assume that a table $\Lambda'$ is obtained from $\Lambda$ by attaching a $1$-entry to one of the rows and $0$-entries to other rows. Then $A(\Lambda')$ is an extremal matrix of deficiency $\delta$ if and only if $A(\Lambda)$ is an extremal matrix of deficiency $\delta$.

Since sufficiency was proved in Theorem \[extrconstrorderproof\], it remains to prove necessity. Following the previous notation, let $B$ be an extremal matrix of order $n+1$ and with an optimal hyperplane cover $\Lambda'$ and let $A$ be the matrix $A(\Lambda)$ of order $n$.

The matrix $A$ has no polydiagonals because the weight of $\Lambda$ is less than $n$. Let us assume that the weight of the optimal polyplex in $A$ is less than $n - \delta$. Then there exists a hyperplane cover $\Lambda''$ of the matrix $A$ with a smaller weight. Attaching to $\Lambda''$ the deleted column of zero and unity entries we obtain some hyperplane cover of $B$ whose weight is smaller than $n+1 - \delta$ that is impossible.

Let us prove the extremality of $A$. Suppose that there exists a hyperplane cover $\Lambda'''$ such that the weight of $\Lambda'''$ is less than $n$ and $A$ is strictly contained in $A(\Lambda''')$. If we attach to the table $\Lambda'''$ the column in which tables $\Lambda$ and $\Lambda'$ differ, then we get a hyperplane cover with weight less than $n+1$ for a matrix strictly containing the matrix $B$. We again have a contradiction with the extremality of $B$.

The third clause of Construction \[extrconstrorder\] is again not reversible that can be illustrated by a number of examples. The smallest example is the first $3$-dimensional extremal matrix of order $3$ from the list of extremal matrices in Appendix.

Extremal matrices with two-value optimal hyperplane covers
----------------------------------------------------------

In this paragraph we consider one special class of extremal matrices, namely extremal matrices that have optimal hyperplane covers $\Lambda$ for which all $\lambda_{i,j}$ are equal to $0$ or $\lambda$. We give a complete description of this class of matrices and their optimal hyperplane covers and prove that all conjectures from Section \[problemsection\] are true for such matrices.

We start with a characterization of hyperplane covers $\Lambda$ with entries $\lambda_{i,j} \in \{ 0, \nicefrac{1}{m}\}$ for which matrices $A(\Lambda)$ contain a polyplex of the same weight as $\Lambda$.

\[polyplexin1m\] Given $m \in \mathbb{N}$, $m < d$, let $\Lambda$ be a hyperplane cover of a $d$-dimensional matrix $A(\Lambda)$ of order $n$ with entries $\lambda_{i,j} \in \{ 0, \nicefrac{1}{m}\}$ and let the weight $W$ of $\Lambda$ be not greater than $n$. The matrix $A(\Lambda)$ has a polyplex of weight $W$ if and only if the number of nonzero entries in each row of $\Lambda$ is not greater than $W$.

Let $t_i$ denote the number of nonzero entries in the $i$-th row of $\Lambda$. Then $W = \sum\limits_{i=1}^ d t_i/m$. In the matrix $A(\Lambda)$ we look for a polyplex $K$ whose entries equals $x_{i_1,\ldots,i_m}$ in indices covered with weight $\nicefrac{1}{m}$ by hyperplanes of directions $i_j$, where $j = 1, \ldots, m$ and $m < d$, and with weight $0$ by hyperplanes of other directions. All other entries of $K$ we set to be zero.

In Section \[condsection\] we stated that the existence of a polyplex of weight $W$ in $A(\Lambda)$ is equivalent to existence of a nonnegative solution of some system of linear equations. Using the introduced notation, we write this system for our hyperplane cover $\Lambda$:

$$\begin{gathered}
 \label{system1m}
\sum\limits_{i_j = i \mbox{ for some } j} \frac{x_{i_1, \ldots, i_m}}{t_i} \prod\limits_{j=1}^m t_{i_j} \frac{\prod\limits_{l=1}^d (n-t_l)}{\prod\limits_{j=1}^m (n-t_{i_j})} = 1 \mbox{ for all } i = 1, \ldots, d;  \\
\sum\limits_{i_1, \ldots, i_m} x_{i_1, \ldots, i_m} \prod\limits_{j=1}^m t_{i_j} \frac{\prod\limits_{l=1}^d (n-t_l)}{\prod\limits_{j=1}^m (n-t_{i_j})}  = W.\end{gathered}$$

Application to this system the following transformation of variables $$z_{i_1, \ldots, i_m} = x_{i_1, \ldots, i_m} \prod\limits_{j=1}^m t_{i_j} \frac{\prod\limits_{l=1}^d (n-t_l)}{\prod\limits_{j=1}^m (n-t_{i_j})}$$ give us the system $$\begin{gathered}
\sum\limits_{i_j = i \mbox{ for some } j} z_{i_1, \ldots, i_m} = t_i \mbox{ for all } i = 1, \ldots, d;  \\\sum\limits_{i_1, \ldots, i_m} z_{i_1, \ldots, i_m} = W.\end{gathered}$$ Note that for the solvability of this system in nonnegative values $z_{i_1, \ldots, i_m}$ it is necessary that each $t_i$ is not greater than $W$. Sufficiency of this condition can be shown by the induction on $d$: for a minimal $t_i$, we set all $z_{i_1, \ldots, i_m}$ in the $i$-th equation to be the same and reduce this system to a system with fewer equations and with a modified right hand side.

With the help of this lemma we state that there is a one-to-one correspondence between the set of nonequivalent $d$-dimensional extremal matrices of order $n$ whose optimal hyperplane covers contain only two different entries and the set of Young diagrams with $mn-1$ cells, at most $n-1$ columns and at most $d$ rows (where $d > m$).

\[allequalconstr\]

1.  If a hyperplane cover $\Lambda$ of weight $n - \nicefrac{1}{m}$ and with entries $\lambda_{i,j} \in \{0, \nicefrac{1}{m}\}$ has at least one zero in each row then $\Lambda$ is the unique optimal hyperplane cover of the $d$-dimensional extremal matrix $A = A(\Lambda)$ of order $n$ and deficiency of $\delta = \nicefrac{1}{m}$.

2.  There are no extremal matrices with a two-value optimal hyperplane cover that are not given by the previous clause.

1\. By conditions of the theorem, each row of $\Lambda$ has at most $n-1$ nonzero entries that is not greater than its weight $n - \nicefrac{1}{m}$. So Lemma \[polyplexin1m\] implies that $\Lambda$ is an optimal hyperplane cover of the matrix $A = A(\Lambda)$.

Let us proof that the matrix $A$ is extremal. Suppose $\alpha$ is an index covered by $\Lambda$ with weight less than $1$. Without loss of generality, we can assume that $\alpha$ is covered with weight $1 - \nicefrac{1}{m}$. Indeed, if $\alpha$ is covered with a smaller weight then, since nonzero entries occupy at least $m$ rows of $\Lambda$, we can easily find an index $\beta$ covered with weight $1 - \nicefrac{1}{m}$ and for which the submatrix $A_\beta$ is contained in the submatrix $A_\alpha$. It remains to note that the submatrix $A_\alpha$ has a hyperplane cover of weight $n-1$ that satisfies the condition of Lemma \[polyplexin1m\], therefore $A_{\alpha}$ contains a polydiagonal.

The uniqueness of the optimal hyperplane cover $\Lambda$ follows from Proposition \[optuniupper\].

2\. Assume that $\Lambda$ is an optimal hyperplane cover of some $d$-dimensional extremal matrix $A$ of order $n$ such that all $\lambda_{i,j} \in \{0, \lambda \}$ for some $\lambda >0$. Let us show that $\Lambda$ satisfies all conditions of Clause $1$.

By Theorem \[slackuse\], there exists an index covered with weight $1$ by $\Lambda$. It yields that $\lambda = \nicefrac{1}{m}$ for some $m \in \mathbb{N}$. Proposition \[zeroexistextr\] claims that each row of $\Lambda$ has at least one $0$-entry. At last, if the weight of $\Lambda$ is less than $n - \nicefrac{1}{m}$ then we change one of its zero entry to $\nicefrac{1}{m}$ and obtain a hyperplane cover of some matrix that contains $A$ and does not have a polydiagonal: a contradiction to the extremality of $A$.

As an application of the proposed constructions, we give a characterization of all extremal matrices of deficiencies $1$ and $\nicefrac{1}{2}$.

\[biglambdachar\]

1.  There is a one-to-one correspondence between nonequivalent $d$-dimensional extremal matrices of order $n$ and of deficiency $1$ and the Young diagrams with $n-1$ cells and no more than $d$ rows.

2.  $\Lambda$ is the optimal hyperplane cover of a $d$-dimensional extremal matrix of order $n$ and deficiency $\nicefrac{1}{2}$ if and only if all $\lambda_{i,j} \in \{ 0, \nicefrac{1}{2}, 1 \}$, weight of $\Lambda$ is $n - \nicefrac{1}{2}$ and the number of $\nicefrac{1}{2}$-entries in each row of $\Lambda$ is less than the number of $\nicefrac{1}{2}$-entries in the union of all other rows.

The first clause is an immediate corollary of Theorems \[bigdeltalambda\] and \[allequalconstr\]. For the second clause we additionally use Theorem \[onereduction\].

To diagonal extremality of extremal matrices {#diagextrsection}
============================================

In this section we consider properties and questions related to diagonal extremality and prove that all constructions in this paper produce diagonally extremal matrices.

By the definition, each diagonally extremal matrix is extremal. Also in Section \[problemsection\] we put forward a conjecture that the sets of extremal and diagonally extremal matrices coincide.

On the way to prove Conjecture \[diagextrcon\] it is reasonable to start with its weaker version.

\[weakening Conjecture \[diagextrcon\]\] \[minorcon\] If $A$ is an extremal matrix and $a_{\alpha} = 0$ then the submatrix $A_\alpha$ contains a polydiagonal.

On the other hand, Conjectures \[diagextrcon\] and \[minorcon\] may turn out to be equivalent if one more conjecture is true.

\[connecting Conjectures \[diagextrcon\] and \[minorcon\]\] \[diagincompcon\] Assume that $A$ has a polydiagonal and $A = A(\Lambda)$ for some hyperplane cover $\Lambda$. Then $A$ contains a diagonal.

Note that Conjecture \[diagincompcon\] claims that the linear programming problem (1) on the maximum weight of polyplexes stated for multidimensional matrices defined by some hyperplane cover and having a polydiagonal has not only a fractional but also integer solution.

We start the proof part this section with showing that Conjecture \[minorcon\] holds for some zero entries of extremal matrices.

\[supporting Conjecture \[minorcon\]\] \[extrminor\] Suppose that $\Lambda$ is an optimal hyperplane cover of an extremal $d$-dimensional matrix $A$ of order $n$ and deficiency $\delta$. If for index $\beta$, where $a_\beta = 0$, there exists an index $\alpha$ covered by $\Lambda$ with weight $1 - \delta$ and such that $\lambda_{i,\beta_i} \leq \lambda_{i,\alpha_i}$ for all $i = 1, \ldots,d$ then the submatrix $A_\beta$ has a polydiagonal.

Since the submatrix $A_\beta$ contains the submatrix $A_\alpha$, if $A_{\alpha}$ has a polydiagonal then $A_{\beta}$ has a polydiagonal too. So let us prove that there is a polydiagonal in the submatrix $A_\alpha$.

Let $B$ denote the matrix obtained from $A$ by changing a zero entry $a_\alpha$ to a unity one. Since $A$ is an extremal matrix, the matrix $B$ has a polydiagonal. Let $\Lambda'$ be a hyperplane cover of the matrix $B$ that coincide with $\Lambda$ in all entries except for $\lambda_{1,\alpha_1}' = \lambda_{1,\alpha_1} + \delta$. Note that $\Lambda'$ has the weight $n$, so it is an optimal hyperplane cover of $B$.

Extremality of the matrix $A$ implies that for every polydiagonal $K$ in $B$ it holds that $k_{\alpha} >0$. Assume that for some polydiagonal $K$ in $B$ we have $k_{\alpha} < 1$. Then there is another index $\gamma$ such that $k_\gamma >0$ in hyperplane $\Gamma_{1, \alpha_1}$. By Theorem \[slackuse\], index $\gamma$ is covered with weight $1$ by every optimal hyperplane cover of $B$ but the hyperplane cover $\Lambda'$ covers it with weight at least $1+ \delta$: a contradiction.

Next we prove that Constructions \[extrconstrdim\] and \[extrconstrorder\] that increase dimension and order of extremal matrices preserve the property of diagonal extremality.

\[supporting Conjecture \[diagextrcon\]\] \[diagextrconstr\] Let $A$ be a diagonally extremal matrix, and let $B$ be an extremal matrix obtained via Construction $\ref{extrconstrdim}$ or $\ref{extrconstrorder}$. Then the matrix $B$ is also diagonally extremal.

If the matrix $B$ is obtained by Construction \[extrconstrdim\] that all its hyperplanes of some direction are exactly the matrix $A$. If we assume the diagonal extremality of $A$, changing a zero entry of $B$ to a unity one gives a diagonal in some hyperplane of $B$. It only remains to expand this diagonal to the whole matrix $B$.

Assume now that the matrix $B$ is given by Construction \[extrconstrorder\]. Returning to the proof of Theorem \[extrconstrorderproof\], note that in Clause 1 and 2 each polydiagonal, arising in $B$ via replacing a zero entry with index $\gamma$ to a unity one, consists of some unity entry $b_{\sigma}$ and some polydiagonal in the submatrix $B_{\sigma} = A$ such that $\gamma \in A$. In addition, in Clause 3 for some cases the submatrix $B_{\gamma}$ strictly contains matrix $A$. So if such operation gives a diagonal in the matrix $A$ then a diagonal also appears in the matrix $B$.

To prove that all extremal matrices with two-value optimal hyperplane covers are diagonally extremal we use the Gale–Ryser theorem. Recall that, given two partitions $r = (r_1,\ldots,r_n)$ and $s = (s_1,\ldots,s_m)$ of the same integer number, partition $r$ *majorizes* $s$ if $r_1 +\cdots +r_k \geq s_1 +\cdots+s_k$ for all $k$. Also if $s$ is a nonincreasing sequence of natural numbers then $s^*$ denotes the sequence such that $s^*_i$ is the number of $j$ such that $s_j \geq i$.

\[galeryser\] Let $r = (r_1,\ldots,r_n)$ and $s = (s_1,\ldots,s_m)$ be two nonincreasing sequences of nonnegative integers each summing to a common value. There exists a $(0,1)$-matrix of size $n \times m$ with row sums $r$ and column sums $s$ if and only if $s^*$ majorizes $r$.

\[supporting Conjecture \[diagextrcon\]\] \[allequaldiagextr\] Let $A$ be an extremal matrix defined by a hyperplane cover $\Lambda$ whose entries have only two values. Then the matrix $A$ is diagonally extremal.

By Theorem \[allequalconstr\], we may assume that all entries of $\Lambda$ are equal to $0$ or $\nicefrac{1}{m}$ and the deficiency $\delta$ is $\nicefrac{1}{m}$. Let $\alpha$ be an index covered by $\Lambda$ with weight less than $1$. As in the proof of Theorem \[allequalconstr\], without loss of generality, we may suppose that $\alpha$ is covered with weight $1-\nicefrac{1}{m}$ by $\Lambda$.

Let $\Lambda_\alpha$ be a hyperplane cover of the sumbatrix $A_\alpha$ obtained from $\Lambda$ by deleting all hyperplanes containing index $\alpha$. Note that the existence of a diagonal in $A_\alpha$ is equivalent to that via rearranging entries of the $\Lambda_\alpha$ within its rows we can put $\Lambda_\alpha$ to some table with all column sums are at least $1$. By the construction, $\Lambda_\alpha$ is a $d \times (n-1)$-table with exactly $m(n-1)$ nonzero entries equal to $\nicefrac{1}{m}$. So if we denote by $r_i$ the number of nonzero entries of $\Lambda_\alpha$ in the $i$-th row and by $s_j = m$ the required number of positive entries in the $j$-column, then from Theorem \[galeryser\] we deduce that there exists a $(0,1)$-matrix with row sums $r$ and column sums $s$. Thus, for every $a_\alpha =0$ the submatrix $A_\alpha$ contains a diagonal.

Theorems \[diagextrconstr\] and \[allequaldiagextr\] implies that all extremal matrices of big deficiencies are diagonally extremal.

\[supporting Conjecture \[diagextrcon\]\] Every extremal matrix of deficiency $1$ or $\nicefrac{1}{2}$ is diagonally extremal.

Let us look in more details at the problem of a diagonal extremality for an extremal matrix $A$ defined by an optimal hyperplane cover $\Lambda$. Following the proof of Theorem \[allequaldiagextr\], we note that the matrix $A$ is diagonally extremal if and only if, for each index $\alpha$ with $a_\alpha = 0$, the entries in the corresponding table $\Lambda_\alpha$ can be rearranged within their rows in such a way so that the sum of entries in each column is at least $1$. After an appropriate normalization, all entries of $\Lambda_\alpha$ may be considered to be integers.

So for effective determining the diagonal extremality by a given optimal hyperplane cover of extremal matrix it would be convenient to have a generalization of the Gale–Ryser theorem for integer nonnegative matrices or at least some sufficient conditions on existence of such matrices with prescribed column sums. Therefore we set up the following problem.

\[related to Conjecture \[diagextrcon\]\] \[diagtableprob\] What are necessary and sufficient conditions on sequences of integers $r^1, \ldots, r^m$ and $s$ for existence of a matrix $M$ such that the $i$-th row of $M$ has exactly $r^j_i$ entries equal $j$ and the sum of entries in the $l$-th column of $M$ equals $s_l$? The similar question for matrices with column sums at least $m$?

Since every nonnegative integer matrix can be considered as a biadjacency matrix of a bipartite multigraph, we may state this problem in terms of valid bipartite multigraph degree sequences.

\[equivalent to \[diagtableprob\]\] Assume that we are given the sets of multiplicities of all edges for one part of vertices and degrees for another part. Does there exist a bipartite multigraph satisfying these degree and multiplicity conditions?

Extremal matrices of small orders
=================================

The main aim of this section is to examine multidimensional extremal matrices of orders $2$ and $3$ in view of the questions and conjectures of Section \[problemsection\]. For this purpose we introduce more definitions.

Firstly, we note that the support of each diagonal in a multidimensional matrix of order $2$ consists of exactly two indices, namely indices $\alpha$ and $\overline{\alpha}$ that are said to be *antipodal*. Let us call a multidimensional $(0,1)$-matrix $A$ of order $2$ *antipodal* if for each pair of antipodal indices $\alpha$ and $\overline{\alpha}$ entries $a_{\alpha}$ and $a_{\overline{\alpha}}$ are different. Note that antipodal matrices are exactly the graph of self-dual boolean functions.

By the definition, every antipodal matrix does not have diagonals, and changing any zero entry to one produces a diagonal. So all antipodal matrices with no polydiagonals are extremal. Let us prove that there are no other extremal matrices of order $2$.

\[supporting Conjecture \[diagextrcon\]\] \[order2char\] Extremal multidimensional matrices of order $2$ are exactly antipodal matrices without polydiagonals.

Suppose that there exists an extremal but not antipodal multidimensional matrix $A$ of order $2$ and with deficiency $\delta$. Then there exists a pair of antipodal indices $\alpha$ and $\overline{\alpha}$ such that $a_{\alpha} = a_{\overline{\alpha}} = 0$.

Let $\Lambda$ be some optimal hyperplane cover of the matrix $A$. Note that the weight $2 - \delta$ of $\Lambda$ is equal to the sum of cover weights of any two antipodal indices. By Theorem \[extrcode\], each of $\alpha$ and $\overline{\alpha}$ is covered by $\Lambda$ with weight less than $1$. Then both of them are covered by $\Lambda$ with weights strictly between $1 - \delta$ and $1$: a contradiction to Proposition \[edgebound\].

An immediate corollary of Theorem \[order2char\] is that every extremal matrix of order $2$ is diagonally extremal. We also would like to note that not every antipodal matrix (even having a stepped structure) does not contain a polydiagonal. The smallest example is the following $6$-dimensional matrix of order $2$, where the support of the polydiagonal is bold. $$A = \left(\begin{array}{cc} 
\begin{array}{cc|cc}
1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ \hline
1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\
\end{array} &
\begin{array}{cc|cc}
1 & 1 & 1 & \mathbb{1} \\ 1 & 0 & \mathbb{1} & 0 \\ \hline
1 & \mathbb{1} & 0 & 0 \\ \mathbb{1} & 0 & 0 & 0 \\
\end{array} \\
~ & ~ \\
\begin{array}{cc|cc}
1 & 1 & 1 & 0 \\ 1 & \mathbb{1} & 0 & 0 \\ \hline
1 & 0 & \mathbb{1} & 0 \\ 0 & 0 & 0 & 0 
\end{array} &
\begin{array}{cc|cc}
0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \hline
0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 
\end{array} 
\end{array}\right).$$

Continuing the topic of diagonal extremality, let us prove that Conjecture \[diagincompcon\] from Section \[diagextrsection\] is true for matrices of order $2$.

\[supporting Conjecture \[diagincompcon\]\] \[diagin2\] Let $A$ be a matrix of order $2$ such that $A = A(\Lambda)$ for some hyperplane cover $\Lambda$ and assume that $A$ contains a polydiagonal. Then $A$ has a diagonal.

Let $\Lambda$ be a hyperplane cover of a minimum weight such that $A = A(\Lambda)$. Since $A$ has a polydiagonal, the weight of an hyperplane cover $\Lambda$ is not less than $2$. Nonexistence of diagonals in $A$ means that each unity entry of $A$ is covered by $\Lambda$ with weight at least $1 + \varepsilon$ for some $\varepsilon > 0$. But in then $\Lambda' = \frac{1}{1+\varepsilon}\Lambda$ is a hyperplane cover of $A$ with a smaller weight and such that $A = A(\Lambda')$ which is impossible.

As a corollary, we have the following alternatives for submatrices of extremal matrices of order $3$ that may help us to prove (or disprove) the diagonal extremality of such matrices.

Let $A$ be an extremal matrix order $3$ and let $a_{\alpha} = 0$.

1.  If the submatrix $A_\alpha$ has a polydiagonal then $A_{\alpha}$ contains a diagonal.

2.  If the submatrix $A_\alpha$ has no polydiagonals then $A_{\alpha}$ is an extremal matrix of order $2$.

1\. Since the submatrix $A_{\alpha}$ has polydiagonal and $A_{\alpha} = A(\Lambda)$ for some hyperplane cover $\Lambda$, Proposition \[diagin2\] gives that $A_{\alpha}$ has a diagonal.

2\. Since $A_{\alpha} = A(\Lambda)$ for some hyperplane cover $\Lambda$ of weight at least $2$ and $A$ has no polydiagonals, we have that the matrix $A$ is antipodal (because there are no two antipodal entries both covered with weights less than $1$). By Theorem \[order2char\], every antipodal matrix of order without polydiagonals is an extremal matrix.

Let us turn back to extremal matrices of order $2$. Besides Construction \[extrconstrdim\], we can propose one more iterative construction giving extremal matrices of order $2$ and of greater dimension. For this aim, we introduce one more notation.

As it was proved in Theorem \[slackuse\], every row of an optimal hyperplane cover $\Lambda$ of any extremal matrix has at least one zero entry. For $d$-dimensional extremal matrices of order $2$ it means that their optimal hyperplane covers $\Lambda$ have not greater than $d$ nonzero entries $\lambda_1, \ldots, \lambda_l$, with all of them located in different rows of $\Lambda$. We will say that $\lambda_1, \ldots, \lambda_l$ are *essential weights* of the optimal hyperplane cover $\Lambda$.

\[extrconst2\] Given an optimal hyperplane cover $\Lambda$ of a $d$-dimensional matrix $A$ of order $2$ and of deficiency $\delta$ with essential weights $\lambda_1, \ldots, \lambda_d$, let the essential weights of the $(d+1) \times 2$-table $\Lambda'$ be $\lambda_1, \ldots, \lambda_{d-1}, \lambda_d - \delta, \delta$.

\[extrconst2proof\] Let $\Lambda$ be an optimal hyperplane cover of a $d$-dimensional extremal matrix $A$ of order $2$ and of deficiency $\delta$ such that there no entries of $A$ covered by $\Lambda$ with weight strictly between $1$ and $1+\delta$. Then the table $\Lambda'$ obtained from $\Lambda$ via Construction $\ref{extrconst2}$ is an optimal hyperplane cover of the $(d+1)$-dimensional extremal matrix $B = A(\Lambda')$ of order $2$ and of deficiency $\delta$.

Since $B$ is defined by a hyperplane cover $\Lambda'$ of weight $2-\delta$, the matrix $B$ has no polydiagonals.

By the construction, the matrix $A$ is contained in the matrix $B$, more specifically, hyperplanes of the direction $d$ of the matrix $A$ are diagonally located in the intersection of the hyperplanes of directions $d$ and $d+1$ in the matrix $B$. So each polyplex $K'$ of weight $2 -\delta$ in $A$ can be put to a polyplex $K'$ of the same weight in the matrix $B$.

To prove the theorem it remains to show that the matrix $B$ is antipodal because in this case Theorem \[order2char\] gives that $B$ is an extremal matrix. If the matrix $B$ is not antipodal then there exists an index $\alpha$ covered by $\Lambda'$ with weight strictly between $1 - \delta$ and $1$. Note that by Proposition \[extrnescond\], the hyperplane cover $\Lambda$ cannot cover $\alpha$ with the same weight as $\Lambda'$, because $\Lambda$ is an optimal hyperplane cover of an extremal matrix. Then by the construction, $\Lambda$ covers $\alpha$ with weight strictly between $1$ and $1 + \delta$ or with weight strictly between $1 - 2\delta$ and $1 - \delta$ but both cases contradicts to the condition of the theorem.

Next we would like to note that this construction may be used for proving Conjectures \[uniquecon\], \[defcon\] and \[multicon\] for matrices of order $2$.

Assume that for every extremal matrix of order $2$ and with deficiency $\delta$ there are no entries covered with weight strictly between $1$ and $1 + \delta$ by their optimal hyperplane covers. Then $\delta = \nicefrac{1}{m}$ for some $m \in \mathbb{N}$, all such extremal matrices have the unique optimal hyperplane covers $\Lambda$, with all entries $\lambda_{i,j}$ being integer multiples of $\delta$.

Construction \[extrconst2\] allows us to obtain extremal matrices of deficiency $\delta$ with a smaller maximum essential weight from a given extremal matrix of deficiency $\delta$. By the condition, we can apply Construction \[extrconst2\] until all essential weights of the resulting extremal matrix are the same. Application of Theorem \[allequalconstr\] completes the proof.

We conclude this section with one more conjecture that possibly allows us to describe all optimal hyperplane covers of extremal matrices of order $2$ in another way.

Let $A$ be an extremal matrix of order $2$ and $K$ is a vertex of a polyhedron of polyplexes in $A$. Then values $k_\alpha$, $\alpha \in supp(K)$ are essential weights of an optimal hyperplane cover for some multidimensional extremal matrix of order $2$.

Acknowledgements {#acknowledgements .unnumbered}
================

This work was funded by the Russian Science Foundation under grant 18-11-00136. The author is a Young Russian Mathematics award winner and would like to thank its sponsors and jury. The author is also grateful to Vladimir N. Potapov and Sergey V. Avgustinovich for useful discussions.

Appendix. List of extremal matrices of small sizes {#appendix.-list-of-extremal-matrices-of-small-sizes .unnumbered}
==================================================

We list all small-sized extremal matrices with their deficiencies $\delta$ and optimal hyperplane covers $\Lambda$ that cannot be obtained by Constructions \[extrconstrdim\], \[extrconstrorder\] and \[extrconst2\] from matrices of smaller dimension or order. We show by bold all indices covered with weight $1$ by hyperplane covers $\Lambda$. With the help of Proposition \[optuniupper\] it can be checked that all these extremal matrices have unique optimal hyperplane covers. Also it can be verified directly that all these matrices are diagonally extremal.

**$3$-dimensional extremal matrix of order $2$**

$$\left( \begin{array}{cc|cc}
1 & \mathbb{1} & \mathbb{1} & 0 \\ \mathbb{1} & 0 & 0 & 0 
\end{array} \right)
~~~~
\Lambda = \left(\begin{array}{cc} \nicefrac{1}{2} & 0 \\ \nicefrac{1}{2} & 0 \\ \nicefrac{1}{2} & 0 \end{array}\right) ~~~~ \delta = \nicefrac{1}{2}.$$

**$4$-dimensional extremal matrix of order $2$**

$$\left( \begin{array}{cc|cc}
1 & 1 & 1 & \mathbb{1} \\ 1 & \mathbb{1} & \mathbb{1} & 0 \\
\hline
\mathbb{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0
\end{array} \right)
~~~~
\Lambda = \left(\begin{array}{cc} \nicefrac{2}{3} & 0 \\ \nicefrac{1}{3} & 0 \\ \nicefrac{1}{3} & 0 \\ \nicefrac{1}{3} & 0 \end{array}\right) ~~~~ \delta = \nicefrac{1}{3}.$$

**$5$-dimensional extremal matrices of order $2$**

$$\left( \begin{array}{cc} 
\begin{array}{cc|cc}
1 & 1 & 1 & 1 \\ 1 & 1 & 1 & \mathbb{1} \\
\hline
1 & 1 & 1 & \mathbb{1} \\ 1 & \mathbb{1} & \mathbb{1} & 0 
\end{array} &
\begin{array}{cc|cc}
\mathbb{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\
\hline
0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0
\end{array} 
\end{array} \right)
~~~~
\Lambda = \left(\begin{array}{cc} \nicefrac{3}{4} & 0 \\ \nicefrac{1}{4} & 0 \\ \nicefrac{1}{4} & 0 \\ \nicefrac{1}{4} & 0 \\ \nicefrac{1}{4} & 0 \end{array}\right) ~~~~ \delta = \nicefrac{1}{4}.$$

$$\left( \begin{array}{cc} 
\begin{array}{cc|cc}
1 & 1 & 1 & 1 \\ 1 & 1 & 1 & \mathbb{1} \\
\hline
1 & \mathbb{1} & \mathbb{1} & 0 \\ \mathbb{1} & 0 & 0 & 0 
\end{array} &
\begin{array}{cc|cc}
1 & \mathbb{1} & \mathbb{1} & 0 \\ \mathbb{1} & 0 & 0 & 0 \\
\hline
0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0
\end{array} 
\end{array} \right)
~~~~
\Lambda = \left(\begin{array}{cc} \nicefrac{1}{2} & 0 \\ \nicefrac{1}{2} & 0 \\ \nicefrac{1}{4} & 0 \\ \nicefrac{1}{4} & 0 \\ \nicefrac{1}{4} & 0 \end{array}\right) ~~~~ \delta = \nicefrac{1}{4}.$$

$$\left( \begin{array}{cc} 
\begin{array}{cc|cc}
1 & 1 & 1 & 1 \\ 1 & 1 & 1 & \mathbb{1} \\
\hline
1 & 1 & \mathbb{1} & 0 \\ 1 & \mathbb{1} & 0 & 0 
\end{array} &
\begin{array}{cc|cc}
1 & \mathbb{1} & 0 & 0 \\ \mathbb{1} & 0 & 0 & 0 \\
\hline
0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0
\end{array} 
\end{array} \right)
~~~~
\Lambda = \left(\begin{array}{cc} \nicefrac{3}{5} & 0 \\ \nicefrac{2}{5} & 0 \\ \nicefrac{2}{5} & 0 \\ \nicefrac{1}{5} & 0 \\ \nicefrac{1}{5} & 0 \end{array}\right) ~~~~ \delta = \nicefrac{1}{5}.$$

**$3$-dimensional extremal matrices of order $3$**

$$\left( \begin{array}{ccc|ccc|ccc}
1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 \\ 
1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 \\ 
\mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 
\end{array} \right)
~~~~
\Lambda = \left(\begin{array}{ccc} \nicefrac{2}{3} & \nicefrac{1}{3} & 0 \\ \nicefrac{2}{3} & \nicefrac{1}{3} & 0 \\ \nicefrac{1}{3} & \nicefrac{1}{3} & 0 \end{array}\right) ~~~~ \delta = \nicefrac{1}{3}.$$ $$\left( \begin{array}{ccc|ccc|ccc}
1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 1 & \mathbb{1} & 0 & 0 & 0 & 0 \\ 
1 & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 
\end{array} \right)
~~~~
\Lambda = \left(\begin{array}{ccc} \nicefrac{3}{4} & \nicefrac{1}{2} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \end{array}\right) ~~~~ \delta = \nicefrac{1}{4}.$$

**$3$-dimensional extremal matrices of order $4$**

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{3}{4} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\ \nicefrac{3}{4} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\ \nicefrac{1}{4} & \nicefrac{1}{4} & \nicefrac{1}{4} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{4}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & \mathbb{1} & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{3}{4} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\ \nicefrac{3}{4} & \nicefrac{1}{4} & \nicefrac{1}{4} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{4} & \nicefrac{1}{4} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{4}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & \mathbb{1} & 1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
\mathbb{1} & \mathbb{1} & 0 & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{1}{2} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{4}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{4}{5} & \nicefrac{3}{5} & \nicefrac{2}{5} & 0 \\ \nicefrac{3}{5} & \nicefrac{1}{5} & \nicefrac{1}{5} & 0 \\ \nicefrac{2}{5} & \nicefrac{2}{5} & \nicefrac{1}{5} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{5}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & \mathbb{1} & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{4}{5} & \nicefrac{3}{5} & \nicefrac{1}{5} & 0 \\ \nicefrac{4}{5} & \nicefrac{2}{5} & \nicefrac{1}{5} & 0 \\ \nicefrac{2}{5} & \nicefrac{1}{5} & \nicefrac{1}{5} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{5}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 \\ 
1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & 0 & 1 & 0 & 0 & 0 & \mathbb{1} & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 0 & 0 & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & \mathbb{1} & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{4}{5} & \nicefrac{2}{5} & \nicefrac{1}{5} & 0 \\ \nicefrac{4}{5} & \nicefrac{2}{5} & \nicefrac{1}{5} & 0 \\ \nicefrac{3}{5} & \nicefrac{1}{5} & \nicefrac{1}{5} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{5}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
\mathbb{1} & \mathbb{1} & 0 & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{3}{5} & \nicefrac{3}{5} & \nicefrac{2}{5} & 0 \\ \nicefrac{3}{5} & \nicefrac{2}{5} & \nicefrac{1}{5} & 0 \\ \nicefrac{2}{5} & \nicefrac{2}{5} & \nicefrac{1}{5} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{5}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & 1 & \mathbb{1} & 0 & 0 & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & \mathbb{1} & 0 & 0 & \mathbb{1} & 0 & 0 & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{3}{5} & \nicefrac{2}{5} & \nicefrac{2}{5} & 0 \\ \nicefrac{3}{5} & \nicefrac{2}{5} & \nicefrac{1}{5} & 0 \\ \nicefrac{3}{5} & \nicefrac{2}{5} & \nicefrac{1}{5} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{5}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & \mathbb{1} & \mathbb{1} & 0 & 1 & 0 & 0 & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{5}{6} & \nicefrac{2}{3} & \nicefrac{1}{2} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{3} & \nicefrac{1}{6} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{6} & \nicefrac{1}{6} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{6}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{5}{6} & \nicefrac{2}{3} & \nicefrac{1}{3} & 0 \\ \nicefrac{2}{3} & \nicefrac{1}{3} & \nicefrac{1}{6} & 0 \\ \nicefrac{1}{3} & \nicefrac{1}{3} & \nicefrac{1}{6} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{6}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & 1 & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & 1 & 1 & 0 & 0 & \mathbb{1} & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & \mathbb{1} & 1 & 1 & 0 & 0 & 1 &\mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & \mathbb{1} & 0 & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{2}{3} & \nicefrac{1}{2} & \nicefrac{1}{3} & 0 \\ \nicefrac{2}{3} & \nicefrac{1}{2} & \nicefrac{1}{3} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{3} & 0 & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{6}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} &\mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
\mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{2}{3} & \nicefrac{1}{2} & \nicefrac{1}{3} & 0 \\ \nicefrac{2}{3} & \nicefrac{1}{2} & \nicefrac{1}{3} & 0 \\ \nicefrac{1}{3} & \nicefrac{1}{3} & \nicefrac{1}{6} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{6}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & \mathbb{1} & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & 1 & 0 & 1 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 0 & 1 & \mathbb{1} & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & \mathbb{1} & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{2}{3} & \nicefrac{1}{2} & \nicefrac{1}{3} & 0 \\ \nicefrac{2}{3} & \nicefrac{1}{3} & \nicefrac{1}{6} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{3} & \nicefrac{1}{3} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{6}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & 1 & 0 & 1 & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 0 & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{5}{7} & \nicefrac{4}{7} & \nicefrac{3}{7} & 0 \\ \nicefrac{4}{7} & \nicefrac{2}{7} & \nicefrac{1}{7} & 0 \\ \nicefrac{3}{7} & \nicefrac{3}{7} & \nicefrac{2}{7} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{7}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 1 & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & \mathbb{1} & 0 & 0 & \mathbb{1} & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{5}{7} & \nicefrac{3}{7} & \nicefrac{1}{7} & 0 \\ \nicefrac{4}{7} & \nicefrac{3}{7} & \nicefrac{2}{7} & 0 \\ \nicefrac{4}{7} & \nicefrac{3}{7} & \nicefrac{2}{7} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{7}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & 1 & \mathbb{1} & 0 & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{7}{8} & \nicefrac{3}{4} & \nicefrac{1}{2} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{4} & \nicefrac{1}{8} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{4} & \nicefrac{1}{8} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{8}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & \mathbb{1} & 0 & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & \mathbb{1} & 0 & 0 & 1 & 0 & 0 & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{3}{4} & \nicefrac{5}{8} & \nicefrac{1}{2} & 0 \\ \nicefrac{1}{2} & \nicefrac{3}{8} & \nicefrac{1}{4} & 0 \\ \nicefrac{1}{2} & \nicefrac{1}{4} & \nicefrac{1}{8} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{8}.$$

$$\left( \begin{array}{cccc|cccc|cccc|cccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 0 & 1 & \mathbb{1} & 0 & 0 \\ 
1 & 1 & 1 & 1 & 1 & 1 & 1 & \mathbb{1} & 1 & \mathbb{1} & 0 & 0 & \mathbb{1} & 0 & 0 & 0 \\ 
1 & 1 & 1 & \mathbb{1} & 1 & 1 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 1 & \mathbb{1} & 0 & \mathbb{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
\end{array} \right)
~~
\Lambda = \left(\begin{array}{cccc} \nicefrac{3}{4} & \nicefrac{1}{2} & \nicefrac{1}{8} & 0 \\ \nicefrac{5}{8} & \nicefrac{1}{2} & \nicefrac{1}{4} & 0 \\ \nicefrac{1}{2} & \nicefrac{3}{8} & \nicefrac{1}{4} & 0 \end{array}\right) ~~ \delta = \nicefrac{1}{8}.$$

[99]{}

R. Aharoni. Ryser’s conjecture for tripartite 3-graphs. *Combinatorica* **21**(1) (2001), 1–4.

R. Aharoni, A. Georgakopoulos, P. Sprüssel. Perfect matchings in $r$-partite $r$-graphs. *European J. Combin.* **30**(1) (2009), 39–42.

R. Aharoni, P.E. Haxell. Hall’s theorem for hypergraphs. *J. Graph Theory* **35** (2000), 83–88.

D. Best, I. M. Wanless. What did Ryser conjecture? ArXiv:1801.02893.

C.A. Floudas, P.M. Pardalos. *Encyclopedia of Optimization.* 2nd edition. Springer, Boston, MA. 2009.

Z. Füredi, J. Kahn, P.D. Seymour. On the fractional matching polytope of a hypergraph. *Combinatorica* **13**(2) (1993), 167–180.

D. Gale. A theorem on flows in networks. *Pacific J. Math.* **7** (1957), 1073–1082.

P.E. Haxell, L. Narins, T. Szabó. Extremal hypergraphs for Ryser’s conjecture: home-base hypergraphs. ArXiv: 1401.0171.

P.E. Haxell, A. D. Scott. On Ryser’s conjecture. *Electron. J. Combin.* **19**(1) (2012), \#P23.

H. Huang, P.-S. Loh, B. Sudakov. The size of a hypergraph and its matching number. *Combin. Probab. Comput.* **21** (2012), 442–450.

P. Keevash, R. Mycroft. *A geometric theory for hypergraph matching.* Memoirs of the American Mathematical Society **233**(1098), 2015.

O.L. Mangasarian. Uniqueness of solution in linear programming. *Linear Algebra Appl.* **25** (1979), 151–162.

V. Rödl, A. Ruciński. Dirac-type questions for hypergraphs – a survey (or more problems for Endre to solve). An Irregular Mind (Szemerédi is 70), *Bolyai Soc. Math. Studies* **21** (2010).

H.J. Ryser. Neuere Probleme in der Kombinatorik. *Vortrage über Kombinatorik Oberwolfach. 22–29 July* (1967), 69–91.

H.J. Ryser. Combinatorial properties of matrices of zeros and ones. *Canad. J. Math.* **9** (1957), 371–377.

A. Schrijver. *Combinatorial Optimization: Polyhedra and Efficiency.* Algorithms and Combinatorics **24**. Springer. 2003.

A. Schrijver. *Theory of Linear and Integer Programming.* John Wiley and Sons Ltd, Chichester, 1986.

A.A. Taranenko. Transversals, plexes, and multiplexes in iterated quasigroups. *Electron. J. Combin.* **25**(4) (2018), \#P4.30.

I.M. Wanless. Transversals in latin squares: a survey. Surveys in Combinatorics 2011, *London Mathematical Society Lecture Note Series* **392** (2011), 403–437.

D.R. Woodall. Vector transversals. *J. Combin. Theory Ser. B* **32** (1982), 189–205.

[^1]: Sobolev Institute of Mathematics, Novosibirsk, Russia. `taa@math.nsc.ru`
