×

Nonnegative square roots of matrices. (English) Zbl 1335.15042

Summary: By the square root of a (square) matrix \(A\) we mean a matrix \(B\) that satisfies \(B^2 = A\). In this paper, we begin a study of the (entrywise) nonnegative square roots of nonnegative matrices, adopting mainly a graph-theoretic approach. To start with, we settle completely the question of existence and uniqueness of nonnegative square roots for 2-by-2 nonnegative matrices. By the square of a digraph \(H\), denoted by \(H^2\), we mean the digraph with the same vertex set as \(H\) such that \((i, j)\) is an arc if there is a vertex \(k\) such that \((i, k)\) and \((k, j)\) are both arcs in \(H\). We call a digraph \(H\) a square root of a digraph \(G\) if \(H^2 = G\). It is observed that a necessary condition for a nonnegative matrix to have a nonnegative square root is that its digraph has a square root, and also that a digraph \(G\) has a square root if and only if there exists a nonnegative matrix \(A\) with digraph \(G\) such that \(A\) has a nonnegative square root. We consider when or whether certain kinds of digraphs (including digraphs that are disjoint union of directed paths and circuits, permutation digraphs or a special kind of bigraphs) have square roots. We also consider when certain kinds of nonnegative matrices (including monomial matrices, rank-one matrices and nilpotent matrices with index two) have nonnegative square roots. A known characterization of loopless digraphs to have square roots, due to F. Escalante et al. [J. Comb. Theory, Ser. B 16, 282–289 (1974; Zbl 0268.05118)], is extended (and amended) to digraphs possibly with loops. Some natural open questions are also posed.

MSC:

15B48 Positive matrices and their generalizations; cones of matrices
05C20 Directed graphs (digraphs), tournaments
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C76 Graph operations (line graphs, products, etc.)

Citations:

Zbl 0268.05118

Software:

mftoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alefeld, G.; Schneider, N., On square roots of \(M\)-matrices, Linear Algebra Appl., 42, 119-132 (1982) · Zbl 0483.15009
[2] Berman, A., Complete positivity, Linear Algebra Appl., 107, 57-63 (1988) · Zbl 0651.15019
[3] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences (1994), SIAM edition, SIAM: SIAM edition, SIAM Philadelphia · Zbl 0815.15016
[4] Berman, A.; Shaked-Monderer, N., Completely Positive Matrices (2003), World Scientific · Zbl 1030.15022
[5] Bóna, M., Combinatorics of Permutations (2012), CRC Press: CRC Press Boca Raton, FL · Zbl 1255.05001
[6] Bru, R.; Canto, R.; Tam, B. S., Predecessor property, fully combinatorial column rank, and the height characteristic of an M-matrix, Linear Algebra Appl., 183, 1-22 (1993) · Zbl 0784.05043
[7] Cayley, A., A memoir on the theory of matrices, Philos. Trans. R. Soc. Lond., 148, 17-37 (1858)
[8] Cayley, A., On the extraction of the square root of a matrix of the third order, Proc. Roy. Soc. Edinburgh, 7, 675-682 (1872) · JFM 07.0067.01
[9] Cecioni, F., Sopra alcune operazioni algebriche sulle matrici, Ann. Sc. Norm. Super. Pisa Cl. Sci., 11, 1-141 (1910) · JFM 41.0193.02
[10] Escalantge, F.; Montejano, L.; Rojano, T., Characterization of \(n\)-path graphs and of graphs having \(n\) th root, J. Combin. Theory Ser. B, 16, 282-289 (1974) · Zbl 0268.05118
[11] Flanders, H., Elementary divisors of AB and BA, Proc. Amer. Math. Soc., 2, 871-874 (1951) · Zbl 0044.00602
[12] Frobenius, G., Über die cogredienten transformation der bilinearen formen, Sitzungsber. Königl. Press. Akad. Wiss., 7-16 (1896) · JFM 27.0079.02
[13] Higham, N. J., Functions of Matrices: Theory and Computation (2008), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1167.15001
[14] Higham, N. J.; Lin, L. J., On \(p\) th roots of stochastic matrices, Linear Algebra Appl., 435, 448-463 (2011) · Zbl 1223.15042
[15] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1990), Cambridge University Press: Cambridge University Press Cambridge
[16] Huang, P.-R., Nonnegative square roots of nonnegative matrices (2014), Tamkang University, Master thesis
[17] Johnson, C. R., Row stochastic matrices that are similar to doubly stochastic matrices, Linear Multilinear Algebra, 10, 113-120 (1981) · Zbl 0455.15019
[18] Johnson, C. R.; Schreiner, E. A., The relationship between AB and BA, Amer. Math. Monthly, 103, 578-582 (1996) · Zbl 0865.15010
[19] Kreis, H., Auflosüng der gleichung \(X^m = A\), Vjschr. Naturforsch. Ges. Zürich, 53, 366-376 (1908) · JFM 39.0214.02
[20] Loewy, R.; London, D., A note on an inverse problems for nonnegative matrices, Linear Multilinear Algebra, 6, 83-90 (1978) · Zbl 0376.15006
[21] Marcus, M.; Minc, H., Some results on doubly stochastic matrices, Proc. Amer. Math. Soc., 69, 571-579 (1962) · Zbl 0107.01403
[22] McDonald, J. J.; Paparella, P., Matrix roots of imprimitive irreducible nonnegative matrices, Linear Algebra Appl., 498, 244-261 (2016) · Zbl 1334.15021
[23] Minc, H., Nonnegative Matrices (1988), Wiley: Wiley New York · Zbl 0638.15008
[24] Richman, D. J.; Schneider, H., Primes in the semigroup of non-negative matrices, Linear Multilinear Algebra, 2, 135-140 (1974)
[25] Suleimanova, H. R., Stochastic matrices with real eigenvalues, Sov. Math. Dokl., 66, 343-345 (1949) · Zbl 0035.20903
[26] Sylvester, J. J., Sur les puissances et les racines de substitutions linéaires, Comptes Rendus, 94, 55-59 (1882) · JFM 14.0099.01
[27] Tam, B.-S., On matrices with cyclic structure, Linear Algebra Appl., 302-303, 377-410 (1999) · Zbl 0945.15009
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.