Congruence numerical ranges and their radii

The earliest congruence numerical range was introduced by Thompson in 1980. Since then, congruence numerical ranges and their radii have been studied by some authors. The purpose of this article is to discuss several aspects of this subject. We survey some known results and propose some problems for furthur study. A few new results are also presented.     

Congruence numerical ranges and their radii

The earliest congruence numerical range was introduced by Thompson in 1980. Since then, congruence numerical ranges and their radii have been studied by some authors. The purpose of this article is to discuss several aspects of this subject. We survey some known results and propose some problems for furthur study. A few new results are also presented.     

Minimum permanents of doubly stochastic matrices with at least one zero entry †

It is shown that the minimum value of the permanent on the n× ndoubly stochastic matrices which contain at least one zero entry is achieved at those matrices nearest to J_n in Euclidean norm, where J_n is the n× nmatrix each of whose entries is n^-1 . In case n ≠ 3 the minimum permanent is achieved only at those matrices nearest J_n ; for n= 3 it is achieved at other matrices containing one or more zero entries as well.     

, Vertex Isoperimetry and Concentration

. This approach refines results relating the spectral gap of a graph to the so-called magnification of a graph. A concentration result involving is also derived. Received July 22, 1998     

The Combinatorics of Biased Riffle Shuffles

Received: September 23, 1997     

Functional centrality in graphs

In this article, we introduce the functional centrality as a generalization of the subgraph centrality. We propose a general method for characterizing nodes in the graph according to the number of closed walks starting and ending at the node. Closed walks are appropriately weighted according to the topological features that we need to measure.     

On the Sparsity Order of a Graph and Its Deficiency in Chordality

Given a graph G on n nodes, let denote the cone consisting of the positive semidefinite matrices (with real or complex entries) having a zero entry at every off-diagonal position corresponding to a non edge of G. Then, the sparsity order of G is defined as the maximum rank of a matrix lying on an extreme ray of the cone . It is known that the graphs with sparsity order 1 are the chordal graphs and a characterization of the graphs with sparsity order 2 is conjectured in [1] in the real case. We show in this paper the validity of this conjecture. Moreover, we characterize the graphs with sparsity order 2 in the complex case and we give a decomposition result for the graphs with sparsity order in both real and complex cases. As an application, these graphs can be recognized in polynomial time. We also indicate how an inequality from [17] relating the sparsity order of a graph and its minimum fill-in can be derived from a result concerning the dimension of the faces of the cone . Received August 31, 1998/Revised April 26, 2000     

Characterization of supercommuting matrices

For a given n–by–n matrix A, we consider the set of matrices which commute with A and all of whose principal submatrices commute with the corresponding principal submatrices of A. The properties of this set are examined, with particular attention to its dimension.     

Extremal matrices in certain determinantal inequalities

The extremal matrices in certain inequalities for determinants of sums are characterized. Related determinantal inequalities involving Hadamard products of positive definite matrices are presented. These inequalities are easy consequences of majorization results recently obtained by Ando and Visick.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Numerical ranges in physics

Some examples of the incidence of Numerical Ranges in Physics are discussed. The Thermodynamical Inequality is deduced using the theory of Numerical Ranges. The Peierls-Bogoliubov inequality is obtained from the Thermodynamical Inequality. The formalism of Thermo Field Dynamics is summarized in the same framework.     

The Cheeger Constant, the Heat Kernel, and the Green Kernel of an Infinite Graph

 This paper gives a new approach to estimate the Cheeger constant, the heat kernel, and the Green kernel of the combinatorial Laplacian for an infinite graph. Received March 12, 2001; in final form July 11, 2002     

A Theorem of Truemper

Received November 5, 1997     

On the third largest Laplacian eigenvalue of a graph

In this article, a sharp lower bound for the third largest Laplacian eigenvalue of a graph is given in terms of the third largest degree of the graph.     

Characterization of supercommuting matrices

For a given n-by-n matrix A, we consider the set of matrices which commute with A and all of whose principal submatrices commute with the corresponding principal submatrices of A. The properties of this set are examined, with particular attention to its dimension.     

Lucas' theorem refined ∗

We prove a refined version of the classical Lucas' theorem: if p is a polynomial with zeros a ₁,…,a _n+1 all having modulus one and φis the Blaschke product whose zeros are those of the derivative p ¹, then the compression of the shift S(φ) has its numerical range circumscribed about by the (n+ l)-gon a ₁…a _n+1 with tangent points the midpoints of then+ l sides of the polygon. This is proved via a special matrix representation of S(φ) and is a generalization of the known case for n= 2.     

Arithmetic-Geometric Mean determinantal identity

In this paper, we give a generalization of a determinantal identity posed by Charles R. Johnson about minors of a Toeplitz matrix satisfying a specific matrix identity. These minors are those appear in the Dodgson’s condensation formula.     

On the generalized indices of boolean matrices

We characterize completely those Boolean matrices with the largest generalized indices in the class of Boolean matrices and in the class of reducible Boolean matrices and derive a new upper bound for the generalized index in terms of period. We also generalize the upper and lower multiexponents of primitive Boolean matrices to general Boolean matrices.     

Construction of determinantal representation of trigonometric polynomials

For a pair of n×n Hermitian matrices H and K, a real ternary homogeneous polynomial defined by F(t,x,y)=det(tI_n+xH+yK) is hyperbolic with respect to (1,0,0). The Fiedler conjecture (or Lax conjecture) is recently affirmed, namely, for any real ternary hyperbolic polynomial F(t,x,y), there exist real symmetric matrices S₁ and S₂ such that F(t,x,y)=det(tI_n+xS₁+yS₂). In this paper, we give a constructive proof of the existence of symmetric matrices for the ternary forms associated with trigonometric polynomials.     

Subspaces where an immanant is convertible into its conjugate ∗

Let n≥5 and let be an irreducible nonlinear character of S_n such that whenever σ is a transposition or a cycle of length three; furthermore let T_n be the (0, 1)-matrix of order n that has ones exactly on and below the upper neighbours of the main diagonal and denote by E_ij the matrix of order n with 1 in position (i, j) and 0 elsewhere.

Given i,jε{1,…,n}, with i+1<j, we prove that if j?i≠3, then in the subspace M_n (T_n +E_ij there exist matrices for which the immanant is not convertible into the immanant by sign-affixing. Abusing language, we say that the space is -inconvertible, and show that spaces M_n (T_n +E₂₅ ) and M_n (T_n +E_n?3,n ). We also state some sufficient fonditions for the subspace M_n (T_n ) to be external convertible.

With some exceptions our theorems say that the coordinate subspaces found for the conversion of the permanent into the determinant by Gibson around 1970 are also best possible for other immanants.