Doubly stochastic matrices of trees

In this paper, we obtain sharp upper and lower bounds for the smallest entries of doubly stochastic matrices of trees and characterize all extreme graphs which attain the bounds. We also present a counterexample to Merris’ conjecture on relations between the smallest entry of the doubly stochastic matrix and the algebraic connectivity of a graph in [R. Merris, Doubly stochastic graph matrices II, Linear Multilinear Algebr. 45 (1998) 275–285].     

A problem of Mirsky concerning nonsingular doubly stochastic matrices

The paper presents a new constructive proof of a theorem of Hardy, Littlewood, and Polya relating vector majorization and doubly stochastic matrices. Conditions on the vectors which guarantee that the corresponding matrices will be direct sums are given. These two results are applied to solve the problem, posed by Mirsky, of characterizing those majorization relations for which there is a corresponding doubly stochastic matrix which is nonsingular.     

Permanents of special classes of doubly stochastic matrices

We identify the doubly stochastic matrices with at least one zero entry which are closest in the Euclidean norm to J_n, the matrix with each entry equal to 1/n, and we show that at these matrices the permanent function has a relative minimum when restricted to doubly stochastic matrices having zero entries.     

Theorems on partitioned matrices revisited and their applications to graph spectra

Some old results about spectra of partitioned matrices due to Goddard and Schneider or Haynsworth are re-proved. A new result is given for the spectrum of a block-stochastic matrix with the property that each off-diagonal block has equal entries and each diagonal block has equal diagonal entries and equal off-diagonal entries. The result is applied to the study of the spectra of the usual graph matrices by partitioning the vertex set of the graph according to the neighborhood equivalence relation. The concept of a reduced graph matrix is introduced. The question of when n-2 is the second largest signless Laplacian eigenvalue of a connected graph of order n is treated. A recent conjecture posed by Tam, Fan and Zhou on graphs that maximize the signless Laplacian spectral radius over all (not necessarily connected) graphs with given numbers of vertices and edges is refuted. The Laplacian spectrum of a (degree) maximal graph is reconsidered.     

紧图的两个结果及其应用

双随机矩阵有许多重要的应用, 紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值． 确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果：任意紧图与任意多个孤立点的不交并是紧图;任意紧图的每一个顶点上各增加一条悬挂边的图是紧图． 利用这两个结果,从已知紧图可构造出无穷多个紧图族．     

A Birkhoff Theorem for Doubly Stochastic Matrices with Vector Entries

The concept of a doubly stochastic matrix whose entries come from a convex subset of the unit square is defined. It is proved that the only convex subsets of the unit square which contain (0,0) and (1, 1) and allow an extension of Birkhoff's characterization of the extreme points of the set of doubly stochastic matrices are parallelograms. A sufficient condition is given for a matrix to be extreme when the convex subset is not a parallelogram.     

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.     

Products of basic doubly stochastic matrices over a field

It is shown that if n?3, then every doubly stochastic matrix of order n over a field F is a product of doubly stochastic matrices with exactly two nonzero off- diagonal entries if and only if the characteristic of F is not 2 and F has more than three elements. A number of related results are also obtained.     

The completely positive and doubly nonnegative completion problems

We prove the following. Let G be an undirected graph. Every partially specified symmetric matrix, the graph of whose specified entries is G and each of whose fully specified submatrices is completely positive (equal to BB^T for some entrywise nonnegative matrix B), may be completed to a completely positive matrix if and only if G is a block-clique graph (a chordal graph in which distinct maximal cliques overlap in at most one vertex). The same result holds for matrices that are doubly nonnegative (entrywise nonnegative and positive semidefinite).     

Minimum Permanents of Tridiagonal Doubly Stochastic Matrices

We determine the minimum permanents and minimizing matrices of the tridiagonal doubly stochastic matrices and of certain doubly stochastic matrices with prescribed zero entries.     

Minimum Permanents of Tridiagonal Doubly Stochastic Matrices

We determine the minimum permanents and minimizing matrices of the tridiagonal doubly stochastic matrices and of certain doubly stochastic matrices with prescribed zero entries.     

Minimum permanents of doubly stochastic matrices with zero main diagonal

The permanent function on the set of n×n doubly stochastic matrices with zero main diagonal attains a strict local minimum at the matrix whose off diagonal entries are all equal to 1/(n-1).     

On the Representation of Doubly Stochastic Matrices as Sums of Permutations

Any doubly stochastic finite matrix with integer entries isthe sum of permutation matrices. A lower bound on how many ofthe permutations are equal is obtained.     

Doubly stochastic graph matrices, II

If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main purpose of this note is to continue the study of the positive definite, doubly stochastic graph matrix (I_n + L(G))-¹= ω(G) = (w_ij). If, for example, w(G) = min w_ij, then w(G)≥0 with equality if and only if G is disconnected and w(G) ≤ l/(n + 1) with equality if and only if G = K_n. If i¦j, then w_ii ≥2wij, with equality if and only if the ith vertex has degree n - 1. In a sense made precise in the note, max w,, identifies most remote vertices of G. Relations between these new graph invariants and the algebraic connectivity emerge naturally from the fact that the second largest eigenvalue of ω(G) is 1/(1 + a(G)).     

A Note on degree antiregular graphs

This note proves a conjecture of Merris that the minimal value of entries of the doubly stochastic matrix of the degree antiregular graph E_n of order n ≥ 3 is equal to (l/2(n + l)).     

On the permanent of doubly stochastic matrices with zero diagonal

The permanent function on the set of n×n doubly stochastic matrices with zero main diagonaln≤4, attains its minimum uniquely at the matrix whose off-diagonal entries are all equal to l/(n-1).     

Doubly stochastic graph matrices,II

If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main purpose of this note is to continue the study of the positive definite, doubly stochastic graph matrix (I_n + L(G))?¹= ω(G) = (w_ij). If, for example, w(G) = min w_ij, then w(G)≥0 with equality if and only if G is disconnected and w(G) ≤ l/(n + 1) with equality if and only if G = K_n. If i¦j, then w_ii ≥2wij, with equality if and only if the ith vertex has degree n - 1. In a sense made precise in the note, max w,, identifies most remote vertices of G. Relations between these new graph invariants and the algebraic connectivity emerge naturally from the fact that the second largest eigenvalue of ω(G) is 1/(1 + a(G)).     

具有位数3和4的双随机循环矩阵中的素元

本文研究了双随机循环矩阵中素元的分类问题．由于任一n阶双随机循环矩阵都可以唯一地表示为移位的n-1次一元多项式,从而可把双随机循环矩阵中素元的分类问题简化为解双随机循环矩阵上的一个方程．应用此原理,本文完全解决了判别具有位数3的n阶双随机循环矩阵是否为素元的问题,并给出了n阶双随机循环矩阵中一类具有位数4的素元．     

Generalization of some results concerning eigenvalues of a certain class of matrices and some applications

In this note, we present a generalization of some results concerning the spectral properties of a certain class of block matrices. As applications, we study some of its implications on nonnegative matrices and doubly stochastic matrices as well as on graph spectra and graph energy.     

广义双随机矩阵反问题及其应用

研究广义双随机矩阵反问题.给出广义双随机矩阵的最小二乘解,得到了解的具体表达形式.并讨论了用广义双随机矩阵构造给定矩阵的最佳逼近问题,给出该问题有解的充分必要条件和解的表达形式.包括算法及数值例子.