首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
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.  相似文献   

2.
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.
  相似文献   

3.
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.  相似文献   

4.
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.  相似文献   

5.
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.  相似文献   

6.
《Optimization》2012,61(6):901-914
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.  相似文献   

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

8.
9.
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.  相似文献   

10.
Gabor frames, unimodularity, and window decay   总被引:4,自引:0,他引:4  
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 γ0 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 γ0 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.  相似文献   

11.
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 \mathfrakgx {\mathfrak{g}^x} in a semisimple Lie algebra \mathfrakg \mathfrak{g} .  相似文献   

12.
13.
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.  相似文献   

14.
15.
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.  相似文献   

16.
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}\}}$ .  相似文献   

17.
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.  相似文献   

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

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

20.
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 ]) .  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号