The nonidealness index of rank-ideal matrices

A polyhedron is integral if all its extreme points have 0, 1 components and in this case the matrix M is called ideal. When Q has fractional extreme points, there are different ways of classifying how far M is away from being ideal, through the polyhedral structure of Q. In this sense, Argiroffo, Bianchi and Nasini (2006) [1] defined a nonidealness index analogous to an imperfection index due to Gerke and McDiarmid (2001) [10].In this work we determine the nonidealness index of rank-ideal matrices (introduced by the authors (2008)). It is known that evaluating this index is NP-hard for any matrix. We provide a tractable way of evaluating it for most circulant matrices, whose blockers are a particular class of rank-ideal matrices, thereby following similar lines as done for the imperfection ratio of webs due to Coulonges, Pêcher and Wagler (2009) [7].Finally, exploiting the properties of this nonidealness index, we identify the facets of the set covering polyhedron of circulant matrices, having maximum strength with respect to the linear relaxation, according to a measure defined by Goemans (1995) [9].     

On packing and covering polyhedra of consecutive ones circulant clutters

Building on work by G. Cornuéjols and B. Novick and by L. Trotter, we give different characterizations of contractions of consecutive ones circulant clutters that give back consecutive ones circulant clutters. Based on a recent result by G. Argiroffo and S. Bianchi, we then arrive at characterizations of the vertices of the fractional set covering polyhedron of these clutters. We obtain similar characterizations for the fractional set packing polyhedron using a result by F.B. Shepherd, and relate our findings with similar ones obtained by A. Wagler for the clique relaxation of the stable set polytope of webs. Finally, we show how our results can be used to obtain some old and new results on the corresponding fractional set covering polyhedron using properties of Farey series. Our results do not depend on Lehman’s work or blocker/antiblocker duality, as is traditional in the field.     

On the first Chvátal closure of the set covering polyhedron related to circulant matrices

We study the set covering polyhedron related to circulant matrices. In particular, our goal is to characterize the first Chvátal closure of the usual fractional relaxation. We present a family of valid inequalities that generalizes the family of minor inequalities previously reported in the literature. This family includes new facet-defining inequalities for the set covering polyhedron.     

On a certain class of nonideal clutters

In this paper we define the class of near-ideal clutters following a similar concept due to Shepherd [Near perfect matrices, Math. Programming 64 (1994) 295-323] for near-perfect graphs. We prove that near-ideal clutters give a polyhedral characterization for minimally nonideal clutters as near-perfect graphs did for minimally imperfect graphs. We characterize near-ideal blockers of graphs as blockers of near-bipartite graphs. We find necessary conditions for a clutter to be near-ideal and sufficient conditions for the clutters satisfying that every minimal vertex cover is minimum.     

Arc transitive covering digraphs and their eigenvalues

We prove that every finite regular digraph has an arc-transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2-arc-transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex-transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc-transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc-transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2-arc-transitive graphs X.     

The bilevel linear/linear fractional programming problem

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. In this paper we consider the bilevel linear/linear fractional programming problem in which the objective function of the first level is linear, the objective function of the second level is linear fractional and the feasible region is a polyhedron. For this problem we prove that an optimal solution can be found which is an extreme point of the polyhedron. Moreover, taking into account the relationship between feasible solutions to the problem and bases of the technological coefficient submatrix associated to variables of the second level, an enumerative algorithm is proposed that finds a global optimum to the problem.     

On a certain class of nonideal clutters

In this paper we define near-ideal clutters following a similar concept due to Shepherd [Mathematical Programming 64 (1994) 295–323] for near-perfect graphs. We find necessary conditions for a clutter to be near-ideal. From these conditions, we prove that near-ideal clutters give a polyhedral characterization for minimally nonideal clutters as well as near-perfect graphs did for minimally imperfect graphs. We characterize near-ideal blockers of graph-clutters as blockers of near-bipartite graphs. We find that two of the necessary conditions of near-ideal clutters become sufficient for clutters such that every minimal vertex cover is minimum.     

DETERMINING THE DISCRIMINATING DOMAIN FOR HYBRID LINEAR DIFFERENTIAL GAME WITH TWO PLAYERS AND TWO TARGETS

This paper studies a bounded discriminating domain for hybrid linear differential game with two players and two targets using viability theory. First of all,we prove that the convex hull of a closed set is also a discriminating domain if the set is a discriminating domain.Secondly,in order to determine that a bounded polyhedron is a discriminating domain,we give a result that it only needs to verify that the extreme points of the polyhedron meet the viability conditions. The difference between our result and the existing ones is that our result just needs to verify the finite points(extreme points) and the existing ones need to verify all points in the bounded polyhedron.     

Comparability for ideals of regular rings

In this paper we investigate necessary and sufficient conditions under which the ideals possess comparability structure. For regular rings, we prove that every square matrix over ideals satisfying general comparability admits a diagonal reduction by quasi-invertible matrices.     

Simultaneous diagonalization of three real symmetric matrices

We formulate and prove necessary and sufficient conditions of simultaneous diagonalization of three real symmetric matrices of regular pencil. The conditions are algebraic and consist, in particular, of two spectral requirements and one matrix equality. For the degenerate matrix pencil we suggest an approach that allows reducing of the analysis to a regular pencil. With the use of obtained theorems we investigate a decomposition of linear gyroscopic system into subsystems of an order not higher than two and the stability of trivial solution to a system.     

Covering properties and square principles

Covering matrices were used by Viale in his proof that the Singular Cardinals Hypothesis follows from the Proper Forcing Axiom and later by Sharon and Viale to investigate the impact of stationary reflection on the approachability ideal. In the course of this work, they isolated two reflection principles, CP and S, which may hold of covering matrices. In this paper, we continue previous work of the author investigating connections between failures of CP and S and variations on Jensen’s square principle. We prove that, for a regular cardinal λ > ω ₁, assuming large cardinals, □(λ, 2) is consistent with CP(λ, θ) for all θ with θ ⁺ < λ. We demonstrate how to force nice θ-covering matrices for λ which fail to satisfy CP and S. We investigate normal covering matrices, showing that, for a regular uncountable κ, □ _κ implies the existence of a normal ω-covering matrix for κ ⁺ but that cardinal arithmetic imposes limits on the existence of a normal θ-covering matrix for κ ⁺ when θ is uncountable. We introduce the notion of a good point for a covering matrix, in analogy with good points in PCF-theoretic scales. We develop the basic theory of these good points and use this to prove some non-existence results about covering matrices. Finally, we investigate certain increasing sequences of functions which arise from covering matrices and from PCF-theoretic considerations and show that a stationary reflection hypothesis places limits on the behavior of these sequences.     

Valuations with preassigned proximity relations

We characterize the infinite upper triangular matrices (which we call formal proximity matrices) that can arise as proximity matrices associated with zero-dimensional valuations dominating regular noetherian local rings. In particular, for every regular noetherian local ring R of the appropriate dimension, we give a sufficient condition for such a formal proximity matrix to be the proximity matrix associated with a real rank one valuation dominating R. Furthermore, we prove that in the special case of rational function fields, each formal proximity matrix arises as the proximity matrix of a valuation whose value group is computable from the formal proximity matrix. We also give an example to show that this is false for more general fields. Finally in the case of characteristic zero, our constructions can be seen as a particular case of a structure theorem for zero-dimensional valuations dominating equicharacteristic regular noetherian local rings.     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.     

Recognizing max-flow min-cut path matrices

Seymour has introduced a class of matrices for which the polyhedron {x | Ax ≥ 1, x ≥ 0} has all integral extreme points. T main result of this paper is a polynomial-time algorithm for determining whether a given matrix is in this class.     

Generalized fuzzy matrices

We give a systematic development of fuzzy matrix theory. Many of our results generalize to matrices over the two element Boolean algebra, over the nonnegative real numbers, over the nonnegative integers, and over the semirings, and we present these generalizations. Our first main result is that while spaces of fuzzy vectors do not have a unique basis in general they have a unique standard basis, and the cardinality of any two bases are equal. Thus concepts of row and column basis, row and column rank can be defined for fuzzy matrices. Then we study Green's equivalence classes of fuzzy matrices. New we give criteria for a fuzzy matrix to be regular and prove that the row and column rank of any regular fuzzy matrix are equal. Various inverses are also studied. In the next section, we obtain bounds for the index and period of a fuzzy matrix.     

On properties of special magic square matrices

By treating regular (or associative), pandiagonal, and most-perfect (MP) magic squares as matrices, we find a number of interesting properties and relationships. In addition, we introduce a new class of quasi-regular (QR) magic squares which includes regular and MP magic squares. These four classes of magic squares are called “special”.We prove that QR magic squares have signed pairs of eigenvalues just as do regular magic squares according to a well-known theorem of Mattingly. This leads to the fact that odd powers of QR magic squares are magic squares which also can be established directly from the QR condition. Since all pandiagonal magic squares of order 4 are MP, they are QR. Also, we show that all pandiagonal magic squares of order 5 are QR but higher-order ones may or may not be. In addition, we prove that odd powers of MP magic squares are MP. A simple proof is given of the known result that natural (or classic) pandiagonal and regular magic squares of singly-even order do not exist.We consider the reflection of a regular magic square about its horizontal or vertical centerline and prove that signed pairs of eigenvalues of the reflected square differ from those of the original square by the factor i. A similar result is found for MP magic squares and a subclass of QR magic squares.The paper begins with mathematical definitions of the special magic squares. Then, a number of useful matrix transformations between them are presented. Next, following a brief summary of the spectral analysis of matrices, the spectra of these special magic squares are considered and the results mentioned above are established. A few numerical examples are presented to illustrate our results.     

Note on: N.E. Aguilera, M.S. Escalante, G.L. Nasini, “The disjunctive procedure and blocker duality”

Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–13] give a generalization of a theorem of Lehman through an extension of the disjunctive procedure defined by Balas, Ceria and Cornuéjols. This generalization can be formulated as(A) For every clutter , the disjunctive index of its set covering polyhedron coincides with the disjunctive index of the set covering polyhedron of its blocker, .In Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–3], (A) is indeed a corollary of the stronger result(B) .Motivated by the work of Gerards et al. [Math. Oper. Res. 28 (2003) 884–885] we propose a simpler proof of (B) as well as an alternative proof of (A), independent of (B). Both of them are based on the relationship between the “disjunctive relaxations” obtained by and the set covering polyhedra associated with some particular minors of .     

Self‐Dual Codes and the Nonexistence of a Quasi‐Symmetric 2‐(37,9,8) Design with Intersection Numbers 1 and 3

We prove that a certain binary linear code associated with the incidence matrix of a quasi‐symmetric 2‐(37, 9, 8) design with intersection numbers 1 and 3 must be contained in an extremal doubly even self‐dual code of length 40. Using the classification of extremal doubly even self‐dual codes of length 40, we show that a quasi‐symmetric 2‐(37, 9, 8) design with intersection numbers 1 and 3 does not exist.     

On the dominating set polytope of web graphs

The dominating set polyhedron of a web graph $W_n^k$ is the set covering polyhedron of a circulant matrix $C_n^{2k+1}$. Working on the set covering polyhedron of general circulant matrices, Argiroffo and Bianchi found a class of valid inequalities, induced by a particular family of circulant minors. The authors also identified sufficient conditions on the minors in order to induce facet defining inequalities. In this work we generalize these results for new valid inequalities associated with every circulant minor. We conjecture that, for any k, the minor inequalities together with the boolean facets are enough to describe the set covering polyhedron of $C_n^k$. This conjecture is true for $k=3$ as Bouchakour et al. prove working in the context of the Minimum Weight Dominating Set problem (MWDSP) on cycles, i.e, on webs $W_n^1$. They also derive the polynomiality of MWDSP on cycles by giving a polynomial separation algorithm for minor inequalities of $C_n^3$. Although the computational complexity of the separation problem of every minor inequality is still an open problem, we can state that the set covering problem on $C_n^k$ matrices is polynomial for a fixed k and obtain polynomial separation algorithms for particular classes of minor inequalities.