The minimum semidefinite rank of a triangle-free graph

We employ a result of Moshe Rosenfeld to show that the minimum semidefinite rank of a triangle-free graph with no isolated vertex must be at least half the number of its vertices. We define a Rosenfeld graph to be such a graph that achieves equality in this bound, and we explore the structure of these special graphs. Their structure turns out to be intimately connected with the zero-nonzero patterns of the unitary matrices. Finally, we suggest an exploration of the connection between the girth of a graph and its minimum semidefinite rank, and provide a conjecture in this direction.     

Linear preservers of minimal rank

It is proved that a linear transformation on the vector space of upper triangular matrices that maps the set of matrices of minimal rank 1 into itself, and either has the analogous property with respect to matrices of full minimal rank, or is bijective, is a triangular equivalence, or a flip about the south-west north-east diagonal followed by a triangular equivalence. The result can be regarded as an analogue of Marcus–Moyls theorem in the context of triangular matrices.     

The geometry of the minimum triangular separation functional

The minimum triangular separation center and measure is used in metrology in testing the “triangularity” of a manufactured object. In this note, the minimum triangular separation measure associated with a planar convex polygon is computed, and the geometry of the functional is illustrated by example.     

On minimum rank and zero forcing sets of a graph

For a graph G on n vertices and a field F, the minimum rank of G over F, written as mr^F(G), is the smallest possible rank over all n×n symmetric matrices over F whose (i,j)th entry (for ) is nonzero whenever ij is an edge in G and is zero otherwise. The maximum nullity of G over F is M^F(G)=n-mr^F(G). The minimum rank problem of a graph G is to determine mr^F(G) (or equivalently, M^F(G)). This problem has received considerable attention over the years. In [F. Barioli, W. Barrett, S. Butler, S.M. Cioab?, D. Cvetkovi?, S.M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanovi?, H. van der Holst, K.V. Meulen, A.W. Wehe, AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628-1648], a new graph parameter Z(G), the zero forcing number, was introduced to bound M^F(G) from above. The authors posted an attractive question: What is the class of graphs G for which Z(G)=M^F(G) for some field F? This paper focuses on exploring the above question.     

关于Schur补应用的一点注记

本文以Schur补的秩可加性为基础，研究任二矩阵的秩之间的关系，讨论了其具有重要意义的若干用例。     

A note on universally optimal matrices and field independence of the minimum rank of a graph

For a simple graph G on n vertices, the minimum rank of G over a field F, written as mr^F(G), is defined to be the smallest possible rank among all n×n symmetric matrices over F whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. A symmetric integer matrix A such that every off-diagonal entry is 0, 1, or -1 is called a universally optimal matrix if, for all fields F, the rank of A over F is the minimum rank of the graph of A over F. Recently, Dealba et al. [L.M. Dealba, J. Grout, L. Hogben, R. Mikkelson, K. Rasmussen, Universally optimal matrices and field independence of the minimum rank of a graph, Electron. J. Linear Algebra 18 (2009) 403-419] initiated the study of universally optimal matrices and established field independence or dependence of minimum rank for some families of graphs. In the present paper, more results on universally optimal matrices and field independence or dependence of the minimum rank of a graph are presented, and some results of Dealba et al. [5] are improved.     

Finite Eulerian posets which are binomial, Sheffer or triangular

In this paper we study finite Eulerian posets which are binomial, Sheffer or triangular. These important classes of posets are related to the theory of generating functions and to geometry. The results of this paper are organized as follows:

•

We completely determine the structure of Eulerian binomial posets and, as a conclusion, we are able to classify factorial functions of Eulerian binomial posets.

•

We give an almost complete classification of factorial functions of Eulerian Sheffer posets by dividing the original question into several cases.

•

In most cases above, we completely determine the structure of Eulerian Sheffer posets, a result stronger than just classifying factorial functions of these Eulerian Sheffer posets.

We also study Eulerian triangular posets. This paper answers questions posed by R. Ehrenborg and M. Readdy. This research is also motivated by the work of R. Stanley about recognizing the boolean lattice by looking at smaller intervals.     

On the minimum semidefinite rank of a simple graph

The minimum semidefinite rank (msr) of a graph is defined to be the minimum rank among all positive semidefinite matrices whose zero/nonzero pattern corresponds to that graph. We recall some known facts and present new results, including results concerning the effects of vertex or edge removal from a graph on msr.     

Remarks on Hua’s matrix equality involving generalized inverses

In this note, some necessary and sufficient conditions for Hua’s matrix equality involving generalized inverses to hold are presented.     

The lattice-theoretic structure of the sets of triangular norms and semi-copulas

The lattice-theoretic structure of the set of semi-copulas and some of its subsets is investigated. As a relevant case, we obtain that the set of commutative semi-copulas is a lattice completion of the set of triangular norms.     

The extent to which subsets are additively closed

Given a finite abelian group G (written additively), and a subset S of G, the size r(S) of the set may range between 0 and ²|S|, with the extremal values of r(S) corresponding to sum-free subsets and subgroups of G. In this paper, we consider the intermediate values which r(S) may take, particularly in the setting where G is Z/pZ under addition (p prime). We obtain various bounds and results. In the Z/pZ setting, this work may be viewed as a subset generalization of the Cauchy-Davenport Theorem.     

The minimum rank problem: A counterexample

We provide a counterexample to a recent conjecture that the minimum rank over the reals of every sign pattern matrix can be realized by a rational matrix. We use one of the equivalences of the conjecture and some results from projective geometry. As a consequence of the counterexample we show that there is a graph for which the minimum rank of the graph over the reals is strictly smaller than the minimum rank of the graph over the rationals. We also make some comments on the minimum rank of sign pattern matrices over different subfields of R.     

A fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

The higher rank numerical range is convex

In this short note we provide the final step in showing that the higher rank numerical range is convex. The previous steps appear in the paper “Geometry of Higher-Rank Numerical Ranges” by Choi, M.-D., Giesinger, M., Holbrook, J.A. and Kribs, D.W.     

The application of the principle of minimum cross-entropy to the characterization of the exponential-type probability distributions

Summary Systematic and simple characterizations are presented for several familiar distributions in exponential family by means of the principle of minimum cross-entropy (minimum discrimination information). The suitable prior distributions and the appropriate constraints on expected values are given for the underlying distributions.     

The rank of sparse random matrices over finite fields

Let M be a random (n×n)-matrix over GF[q] such that for each entry M_ij in M and for each nonzero field element α the probability Pr[M_ij=α] is p/(q−1), where p=(log n−c)/n and c is an arbitrary but fixed positive constant. The probability for a matrix entry to be zero is 1−p. It is shown that the expected rank of M is n−𝒪(1). Furthermore, there is a constant A such that the probability that the rank is less than n−k is less than A/q^k. It is also shown that if c grows depending on n and is unbounded as n goes to infinity, then the expected difference between the rank of M and n is unbounded. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 407–419, 1997     

The rank of a commutative cancellative semigroup

Summary For a commutative cancellative semigroup S, we define the rank of S intrinsically. This definition implies that the rank of S equals the usual rank of its group of quotients. We also characterize the rank in terms of embeddability into a rational vector space of the greatest power cancellative image of S.     

半正定矩阵的Khatri—Rao乘积的广义Schur补

给出了半正定矩阵的Khatri-Rao乘积的广义Schur补的一些矩阵等式与不等式。     

The triangular maps with closed sets of periodic points

In a recent paper we provided a characterization of triangular maps of the square, i.e., maps given by F(x,y)=(f(x),gx(y)), satisfying condition (P1) that any chain recurrent point is periodic. For continuous maps of the interval, there is a list of 18 other conditions equivalent to (P1), including (P2) that there is no infinite ω-limit set, (P3) that the set of periodic points is closed and (P4) that any regularly recurrent point is periodic, for instance. We provide an almost complete classification among these conditions for triangular maps, improve a result given by C. Arteaga [C. Arteaga, Smooth triangular maps of the square with closed set of periodic points, J. Math. Anal. Appl. 196 (1995) 987-997] and state an open problem concerning minimal sets of the triangular maps. The paper solves partially a problem formulated by A.N. Sharkovsky in the eighties. The mentioned open problem, the validity of (P4) ⇒ (P3), is related to the question whether some regularly recurrent point lies in the fibres over an f-minimal set possessing a regularly recurrent point. We answered this question in the positive for triangular maps with nondecreasing fiber maps. Consequently, the classification is completed for monotone triangular maps.