Algebraic connectivity and doubly stochastic tree matrices

In this paper, we investigate the relations between the smallest entry of a doubly stochastic tree matrix associated with a tree and the diameter of the tree, which are used to deal with Merris’s conjecture on the algebraic connectivity and the smallest entries. Further, we present a new upper bound for algebraic connectivity in terms of the smallest entry, which improves Merris’ result.     

Essentially doubly stochastic matrices

In this paper we extend the general theory of essentially doubly stochastic (e.d.s.) matrices begun in earlier papers in this series. We complete the investigation in one direction by characterizing all of the algebra isomorphisms between the algebra of e.d.s. matrices of order n over a field F,E_n(F), and the total algebra of matrices of order n - 1over F,M_n-1(F) We then develop some of the theory when Fis a field with an involution. We show that for any e,f§Fof norm 1,e≠f every e.d.s. matrix in E_n(F) is a unique e.d.s. sum of an e.d.s. e-hermitian matrix and an e.d.s. f-hermitian matrix in E_n(F) Next, we completely determine the cases for which there exists an above-mentioned matrix algebra isomorphism preserving adjoints. Finally, we consider cogredience in E_n(F) and show that when such an adjoint-preserving isomorphism exists and char M_n(F) two e.d.s. e-hermitian matrices which are cogredient in M_n(F) are also cogredient in E_n(F). Using this result, we obtain simple canonical forms for cogredience of e.d.s. e-hermitian matrices in E_n(F) when Fsatisfies special conditions. This ncludes the e.d.s. skew-symmetric matrices, where the involution is trivial and E = -1.     

Directed graphs,Hamiltonicity and doubly stochastic matrices

We consider the Hamiltonian cycle problem embedded in singularly perturbed (controlled) Markov chains. We also consider a functional on the space of stationary policies of the process that consists of the (1,1)‐entry of the fundamental matrices of the Markov chains induced by the same policies. In particular, we focus on the subset of these policies that induce doubly stochastic probability transition matrices, which we refer to as the “doubly stochastic policies.” We show that when the perturbation parameter ? is sufficiently small the minimum of this functional over the space of the doubly stochastic policies is attained very close to a Hamiltonian cycle, provided that the graph is Hamiltonian. We also derive precise analytical expressions for the elements of the fundamental matrix that lend themselves to probabilistic interpretation as well as asymptotic expressions for the first diagonal element, for a variety of deterministic policies that are of special interest, including those that correspond to Hamiltonian cycles. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Extreme symmetric doubly stochastic matrices

We characterize the extreme points of the polytope of symmetric doubly stochastic matrices of a given arbitrary order.     

Subpermanents of doubly stochastic matrices

It is shown that if all subpermaneats of order k of an n × n doubly stochastic matrix are equal for some k ≤ n - 2, then all the entries of the matrix must be equal to 1/n.     

Random doubly stochastic tridiagonal matrices

Let \begin{align*}{\mathcal T}\end{align*}n be the compact convex set of tridiagonal doubly stochastic matrices. These arise naturally in probability problems as birth and death chains with a uniform stationary distribution. We study ‘typical’ matrices T∈ \begin{align*}{\mathcal T}\end{align*}n chosen uniformly at random in the set \begin{align*}{\mathcal T}\end{align*}n. A simple algorithm is presented to allow direct sampling from the uniform distribution on \begin{align*}{\mathcal T}\end{align*}n. Using this algorithm, the elements above the diagonal in T are shown to form a Markov chain. For large n, the limiting Markov chain is reversible and explicitly diagonalizable with transformed Jacobi polynomials as eigenfunctions. These results are used to study the limiting behavior of such typical birth and death chains, including their eigenvalues and mixing times. The results on a uniform random tridiagonal doubly stochastic matrices are related to the distribution of alternating permutations chosen uniformly at random.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 403–437, 2013     

Permanents of doubly stochastic matrices

A conjecture on the permanents of doubly stochastic matrices is proposed. Some results supporting it are presented.     

Products of elementary doubly stochastic matrices

While studying a theorem of Westwerk on higher numerical ranges, we became interested in how the theory of elementary doubly stochastic (e.d.s.) matrices is related to a result of Goldberg and Straus. We show that there exist classes of doubly stochastic (d.s.) matrices of order n≧3 and orthostochastic (o s) matrices of order n≧4 such that the matrices in these classes cannot be represented as a product of e.d.s. matrices. In fact the matrices in these classes do not admit a representation as an infinite limit of a product of e.d.s. matrices.     

Vertex degrees and doubly stochastic graph matrices

In this article, the relationship between vertex degrees and entries of the doubly stochastic graph matrix has been investigated. In particular, we present an upper bound for the main diagonal entries of a doubly stochastic graph matrix and investigate the relations between a kind of distance for graph vertices and the vertex degrees. These results are used to answer in negative Merris' question on doubly stochastic graph matrices. These results may also be used to establish relations between graph structure and entries of doubly stochastic graph matrices. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:104‐114, 2011     

A k-measure of irreducibility and doubly stochastic matrices

A “k-measure of irreducibility” for a doubly stochastic matrix is developed with the aid of some combinatorial results. An application of this measure is established involving a lower bound for the second largest eigenvalue of a symmetric doubly stochastic matrix.     

Matrices which commute with doubly stochastic matrices

The set doubly stochastic matrices which commute with the doubly stochastic matrices of any particular given rank is determined.     

On diagonal products of doubly stochastic matrices

The following result is proved: If A and B are distinct n × n doubly stochastic matrices, then there exists a permutation σ of {1, 2,…, n} such that ∏_ia_iσ(i) > ∏_ib_iσ(i).     

Matrices which commute with doubly stochastic matrices

The set doubly stochastic matrices which commute with the doubly stochastic matrices of any particular given rank is determined.     

Even and odd diagonals in doubly stochastic matrices

The existence of even or odd diagonals in doubly stochastic matrices depends on the number of positive elements in the matrix. The optimal general lower bound in order to guarantee the existence of such diagonals is determined, as well as their minimal number for given number of positive elements. The results are related to the characterization of even doubly stochastic matrices in connection with Birkhoff's algorithm.     

On the Hamiltonicity Gap and doubly stochastic matrices

We consider the Hamiltonian cycle problem embedded in singularly perturbed (controlled) Markov chains. We also consider a functional on the space of stationary policies of the process that consists of the (1,1)‐entry of the fundamental matrices of the Markov chains induced by these policies. We focus on the subset of these policies that induce doubly stochastic probability transition matrices which we refer to as the “doubly stochastic policies.” We show that when the perturbation parameter, ε, is sufficiently small, the minimum of this functional over the space of the doubly stochastic policies is attained at a Hamiltonian cycle, provided that the graph is Hamiltonian. We also show that when the graph is non‐Hamiltonian, the above minimum is strictly greater than that in a Hamiltonian case. We call the size of this difference the “Hamiltonicity Gap” and derive a conservative lower bound for this gap. Our results imply that the Hamiltonian cycle problem is equivalent to the problem of minimizing the variance of the first hitting time of the home node, over doubly stochastic policies. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009