An algorithm for constructing integral row stochastic matrices

Document Type : Research Paper


Department of Mathematics Vali-e-Asr University of Rafsanjan P.O. Box: 7713936417, Rafsanjan, Iran



Let  $\textbf{M}_{n}$ be  the set of all $n$-by-$n$ real  matrices, and let  $\mathbb{R}^{n}$ be  the set of all $n$-by-$1$ real (column) vectors. An $n$-by-$n$ matrix $R=[r_{ij}]$ with nonnegative entries is called row stochastic, if $\sum_{k=1}^{n} r_{ik}$ is equal to 1 for all $i$, $(1\leq i \leq n)$. In fact, $Re=e$, where $e=(1,\ldots,1)^t\in \mathbb{R}^n$.  A matrix $R\in \textbf{M}_{n}$  is called integral row stochastic, if each row has exactly one nonzero entry, $+1$, and other entries are zero.  In the present paper,  we provide an algorithm for constructing integral row stochastic matrices, and also we show the relationship between this algorithm and majorization theory.


[1] T. Ando, Majorization, doubly stochastic matrices, and comparision of eigenvalues, Linear Algebra Appl., 118, (1989), 163-248.
[2] C. Bebeacua, T. Mansour, A. Postnikov, S. Severini, On the X-rays of permutations, Electron. Notes Discrete Math., 20, (2005), 193-203.
[3] R.A. Brualdi, G. Dahl, Constructing (0, 1)-matrices with given line sums and a zero block, in: G.T. Herman, A. Kuba (Eds.), Advances in Discrete Tomography and Its Applications, Birkhuser, Boston, (2007), 113-123.
[4] R.A. Brualdi, E. Fritscher, Hankel and Toeplitz X-rays of permutations, Linear Algebra Appl., 449, (2014), 305-380.
[5] G. Dahl, L-rays of permutation matrices and doubly stochastic matrices, Linear Algebra Appl., 480, (2015), 127-143.
[6] A. Ilkhanizadeh Manesh, Sglt-Majorization on Mn;m and its linear preservers, J. Mahani Mathematical Reserch Center, 7, (2018), 57-125.
[7] A. Ilkhanizadeh Manesh, Right gut-Majorization on Mn;m, Electron. J. Linear Algebra, 31, (2016), 13-26.
[8] A. Mohammadhasani and M. Radjabalipour, The structure of linear operators strongly preserving majorizations of matrices, Electron. J. Linear Algebra, 15, (2006), 266-272.
[9] G.T. Herman, A. Kuba (Eds.), Discrete Tomography Foundations, Algorithms, and Applications, Appl. Numer. Harmon. Anal., Birkhuser, Basel, (1999).
[10] A. W. Marshall, I. Olkin, and B. C. Arnold, Inequalities: Theory of majorization and its applications, Springer, New York, (2011).