A note on the total unimodularity of matrices

A necessary and sufficient characterization of totally unimodular matrices is given which is derived from a necessary condition for total unimodularity due to Camion. This characterization is then used in connection with a theorem of Hoffman and Kruskal to provide an elementary proof of the characterization of totally unimodular matrices in terms of forbidden submatrices due to Camion.     

A constructive method to recognize the total unimodularity of a matrix

Summary A necessary and sufficient condition for a matrix to be totally unimodular is developed in this note. This condition in turn provides a constructive method to recognize the total unimodularity or otherwise of any matrixC with elements 0, 1 or –1.

---

Zusammenfassung In diesem Beitrag wird eine notwendige und hinreichende Bedingung für die vollständige Unimodularität einer Matrix entwickelt. Diese Bedingung führt zu einer brauchbaren Methode, mit der für jede beliebige Matrix C mit den Elementen 0, 1, –1 bestimmt werden kann, ob sie vollständig unimodular ist oder nicht.

     

Local unimodularity of matrix-vector pairs

The main theorem establishes a close relationship between the seemingly separate concepts of balancedness and total unimodularity of {0,1} matrices. The result involves classes of Eulerian matrices, and it is presented using terms “local unimodularity” and “local total unimodularity” recently proposed by Hoffman and Oppenheim.     

Implementation of a unimodularity test

This paper describes implementation and computational results of a polynomial test of total unimodularity. The test is a simplified version of a prior method. The program also decides two related unimodularity properties. The software is available free of charge in source code form under the Boost Software License.     

Total unimodularity and the Euler-subgraph problem

We give a short treatment (including proofs) of all known characterizations by way of forbidden structures of totally unimodular matrices, i.e. matrices whose square minors have determinants of 0, +1, or −1 only. A generalization of a known topological characterization gives rise to a new combinatorial optimization problem which is introduced here and called the Euler-subgraph problem.     

A necessary and sufficient condition for the total unimodularity of a matrix in terms of graph theory

We present a necessary and sufficient condition for an arbitrary matrix A to be totally unimodular. The matrix A is interpreted as the adjacency matrix of a bipartite graph G(A) The total unimodularity of A corresponds to non-existence of a cycle in G(A) which has an odd column valuation and which is equal to the induced subgraph, Some applications of the results are also discussed.     

The use of jacobi's lemma in unimodularity theory

The paper applies Jacobi's fundamental result on minors of the adjoint matrix to obtain properties on determinants of unimodular matrices.     

Total weak unimodularity: testing and applications

The concept of total weak unimodularity for an integral matrix is introduced. Connections are shown to existing and well studied ideas such as TDI and integer rounding. Algorithms are provided for testing total weak unimodularity and producing integral solutions to inequality systems when they exist under the assumption of total weak unimodularity.     

Gabor frames, unimodularity, and window decay

We study time-continuous Gabor frame generating window functions g satisfying decay properties in time and/or frequency with particular emphasis on rational time-frequency lattices. Specifically, we show under what conditions these decay properties of g are inherited by its minimal dual γ⁰ and by generalized duals γ. We consider compactly supported, exponentially decaying, and faster than exponentially decaying (i.e., decay like |g(t)|≤Ce^{−α|t| 1/α} for some 1/2≤α<1) window functions. Particularly, we find that g and γ⁰ have better than exponential decay in both domains if and only if the associated Zibulski-Zeevi matrix is unimodular, i.e., its determinant is a constant. In the case of integer oversampling, unimodularity of the Zibulski-Zeevi matrix is equivalent to tightness of the underlying Gabor frame. For arbitrary oversampling, we furthermore consider tight Gabor frames canonically associated to window functions g satisfying certain decay properties. Here, we show under what conditions and to what extent the canonically associated tight frame inherits decay properties of g. Our proofs rely on the Zak transform, on the Zibulski-Zeevi representation of the Gabor frame operator, on a result by Jaffard, on a functional calculus for Gabor frame operators, on results from the theory of entire functions, and on the theory of polynomial matrices.     

Polynomiality of invariants, unimodularity and adapted pairs

Let \mathfraka \mathfrak{a} be a finite-dimensional Lie algebra and Y( \mathfraka ) Y\left( \mathfrak{a} \right) the \mathfraka \mathfrak{a} invariant subalgebra of its symmetric algebra S( \mathfraka ) S\left( \mathfrak{a} \right) under adjoint action. Recently there has been considerable interest in studying situations when Y( \mathfraka ) Y\left( \mathfrak{a} \right) may be polynomial on index \mathfraka \mathfrak{a} generators, for example if \mathfraka \mathfrak{a} is a biparabolic or a centralizer \mathfrakg^x {\mathfrak{g}^x} in a semisimple Lie algebra \mathfrakg \mathfrak{g} .     

Total unimodularity and the transportation problem: a generalization

Well-known sufficiency conditions for total unimodularity are relaxed to include more general classes of matrices, whose determinants are related to Fibonacci sequences. It is then shown that in order to study determinants of submatrices of the two-commodity transportation problem, one should study precisely these generalized unimodular matrices. (Note that all submatrices of an ordinary transportation problem are unimodular.) This result enables us to establish determinantal values for submatrices of two-commodity transportation problems (in terms of the number of disjoint capacitated routes) and to identify a totally unimodular class of two-commodity transportation problems.     

Complement reducible graphs

In this paper we study the family of graphs which can be reduced to single vertices by recursively complementing all connected subgraphs. It is shown that these graphs can be uniquely represented by a tree where the leaves of the tree correspond to the vertices of the graph. From this tree representation we derive many new structural and algorithmic properties. Furthermore, it is shown that these graphs have arisen independently in various diverse areas of mathematics.     

Complement of forms

The notions of the parallel sum, the parallel difference, and the complement of two nonnegative sesquilinear forms were introduced and studied by Hassi, Sebestyé and de Snoo in Hassi et al. (Oper Theory Adv Appl 198:211–227, 2010) and Hassi et al. (J Funct Anal 257(12):3858–3894, 2009). In this paper we continue these investigations. The Galois correspondence induced by the map ${\mathfrak{m} \mapsto \mathfrak{m}_\mathfrak{t}}$ (where ${\mathfrak{m}_\mathfrak{t}}$ denotes the ${\mathfrak{t}}$ -complement of ${\mathfrak{m}}$ ) is also studied. Inspired by the work of Eriksson and Leutwiler Eriksson and Leutwiler (Math Ann 274:301–317, 1986), we introduce the notion of quasi-unit for nonnegative sesquilinear forms. The quasi-units are characterized by means of the complement and the disjoint part. It is also shown that the ${{\mathfrak{t}}}$ -quasi-units coincide with the extreme points of the convex set ${\mathfrak{z}: 0 \leq \mathfrak{z} \leq \mathfrak{t}\}}$ .     

Complement preserving operators

An operatorTVV on a real inner product space is called complement preserving if, wheneverU is aT-invariant subspace ofV the orthogonal complementU is alsoT-invariant. In this note we obtain some results on such operators.     

Complement on elliptic and hyperbolic inversions

In performing the inversions we analize the case when putu ₁=ax ₁+iby ₁ orax ₁+εby ₁ (i ²=−1,ε ² = 1)x ₁ andy ₁ being orthogonal coordinates of a variable pointM ₁ belonging to a plane whilea andb are positive number which are fixed.     

广义Schur补的广义逆

对四分块矩阵A=A(︿) A(︿,︿′)A(︿′,︿) A(︿′)来说 ,如果 A和 A(︿)都是非奇异的 ,则A- 1 (︿′) =(A/︿) - 1 ,这里 A/ ︿=A(︿′) -A(︿′,︿) A(︿) - 1 A(︿,︿′)是 A(︿)在 A中的 Schur补 .王伯英教授指出上述等式 ,对半正定的 Hermitian矩阵而言 ,一般也是不能推广到 Moore-Penrose逆上去的 .在某些限制条件下 ,我们证明了广义逆的主子矩阵与广义 Schur补的关系是密切的 ,它使经典结果成为特例     

具有八个节点的自补图

In this note we deduce that there are exactly 10 self complement graphs on 8 vertices (G=G), which is characterized in the sort of degree sequences . It is a correction to the assertation made by Harary ( [ 1 ]) .