Some applications of doubly stochastic matrices. (English) Zbl 0657.15016

Author’s summary: Primarily two applications of doubly stochastic matrices and related matrices are discussed. The first concerns a topic in communication theory called satellite-switched, time-division multiple-access systems, and it is attempted to illuminate some results which have occurred in the engineering literature. The second concerns a recent notion of a doubly stochastic automorphism of a graph. Several new theorems about doubly stochastic automorphisms of certain classes of graphs are proved, and in particular, a theorem of which Birkhoff’s theorem for doubly stochastic matrices is a special case, is obtained.
Reviewer: G.Sierksma


15B51 Stochastic matrices
94A05 Communication theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI


[1] Bongiovanni, G.; Coppersmith, D.; Wong, C.K., An optimal time slot assignment algorithm for an SS/TDMA system with variable number of transponders, IEEE trans. comm. com., 29, 721-726, (1981)
[2] Brualdi, R.A.; Gibson, P.M., The convex polyhedron of doubly stochastic matrices I: applications of the permanent function, J. combin. theory ser. A, 22, 194-230, (1977) · Zbl 0355.15013
[3] Brualdi, R.A.; Lee, G.M., On the truncated assignment polytope, Linear algebra appl., 19, 33-62, (1978) · Zbl 0373.52005
[4] Brualdi, R.A., Notes on the Birkhoff algorithm for doubly stochastic matrices, Canad. math. bull., 25, 2, 191-199, (1982) · Zbl 0484.15018
[5] Folkman, J.; Fulkerson, D.R., Edge colorings in bipartite graphs, (), 561-577 · Zbl 0204.57002
[6] Gopal, I.S.; Wong, C.K., Minimizing the number of switchings in an SS/TDMA system, IEEE trans. comm. com., 33, 497-501, (1985)
[7] Hwang, S.-G., A note on a conjecture on permanents, Linear algebra appl., 76, 31-44, (1986) · Zbl 0589.15016
[8] Jurkat, W.B.; Ryser, H.J., Term ranks and permanents of nonnegative matrices, J. algebra, 5, 342-357, (1967) · Zbl 0178.03302
[9] Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart, and Winston New York · Zbl 0358.68059
[10] Lewandowski, J.L.; Liu, C.L., SS/TDMA satellite communications with k-permutation switching modes, SIAM J. algebraic discrete methods, 8, (1987) · Zbl 0636.90040
[11] Ryser, H.J., Combinatorial mathematics, () · Zbl 0112.24806
[12] Tinhofer, G., Graph isomorphism and theorems of Birkhoff type, Computing, 36, 285-300, (1986) · Zbl 0581.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.