کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4598919 | 1631110 | 2015 | 24 صفحه PDF | دانلود رایگان |
Let R=(r1,r2,…,rm)R=(r1,r2,…,rm) and S=(s1,s2,…,sn)S=(s1,s2,…,sn) be nonnegative integral vectors. The class A1(R,S)A1(R,S) of (0,1)(0,1)-matrices with row sum vector R, column sum vector S , and no two consecutive 1's in any column is introduced. Matrices in this class correspond to certain tilings of rectangles by vertical dimers and monomers and arise in the inverse eigenvalue problem for graphs. The main theorem gives necessary and sufficient conditions for the class A1(R,S)A1(R,S) to be nonempty. The conditions can be expressed as a system of majorizations in the spirit of the Gale–Ryser theorem. The class A1(R,S)A1(R,S) is associated with a type of interchange graph, which is proved to be connected. Also, in the case when A1(R,S)A1(R,S) contains a single matrix, the structure of this matrix is identified.
Journal: Linear Algebra and its Applications - Volume 485, 15 November 2015, Pages 503–526