# Nonnegative Combined Matrices

Authors: Rafael Bru; Maria T. Gassó; Isabel Giménez; Máximo Santana
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The combined matrix of a nonsingular real matrixA is the Hadamard (entrywise) product A
∘
A
-
1
T. It is well known that row (column) sums of combined matrices are constant and equal to one. Recently, some results on combined matrices of different classes of matrices have been done. In this work, we study some classes of matrices such that their combined matrices are nonnegative and obtain the relation with the sign pattern of A. In this case the combined matrix is doubly stochastic.


---

## Body

## 1. Introduction

Fiedler and Markham [1] studied matrices of the form C
(
A
)
=
A
∘
(
A
-
1
)
T, that is, the combined matrix of A, where A is a nonsingular matrix and ∘ means the Hadamard product. Combined matrices appear in the chemical literature where they represent the relative gain array (see [2]). Furthermore, the combined matrix gives the relation between the eigenvalues and diagonal entries of a diagonalizable matrix (see [3]). Results for the combined matrix of a nonsingular matrix and also for the Hadamard product A
∘
A
-
1 have been obtained, for instance, in [1] where the behavior of the diagonal entries of the combined matrix of a nonsingular matrix was completely described and in [4] for the positive definite case.It is well known [3] that the row and column sums of a combined matrix are always equal to one. Then, if C
(
A
) is a nonnegative matrix, it has interesting properties and applications since it is a doubly stochastic matrix. For instance, in [5], there are two applications: the first one concerning a topic in communication theory called satellite-switched and the second concerning a recent notion of doubly stochastic automorphism of a graph. Recently, in [6], some implications on nonnegative matrices, doubly stochastic matrices, and graph theory, namely, graph spectra and graph energy, are presented.Here, we focus our work on studying which matrices have nonnegative combined matrices. More precisely, we study the combined matrix of different classes of matrices such as totally positive and totally negative matrices and also whenA is totally nonnegative and totally nonpositive.


## 2. Notation and Previous Results

Unless otherwise indicated, in this work all square matricesA are n
×
n nonsingular and real. Given an n
×
n matrix A, we denote by N the subset of indexes {
1
,
…
,
n
}. For the subsets α
,
β
⊆
N, the submatrix with rows lying in the subset α and columns in the subset β is denoted by A
[
α
,
β
], and the principal submatrix A
[
α
,
α
] is abbreviated to A
[
α
]. Similarly, A
(
α
∣
β
) denotes the submatrix obtained from A by deleting rows lying in α and columns in β, and A
(
α
∣
α
) is abbreviated to A
(
α
). Then, A
(
i
∣
j
) denotes the submatrix obtained from A by deleting row i and column j, and A
[
i
,
j
]
=
a
i
j. Moreover, A
i
j denotes the (
i
,
j
) minor; that is, A
i
j
=
det
⁡
A
(
i
∣
j
).To avoid confusion with other matrices we will say thatA is a nonnegative (positive) matrix if it is entrywise nonnegative (positive); that is, a
i
j
≥
0 (a
i
j
>
0) for all i
,
j
∈
N, and we will denote it by A
≥
0
(
A
>
0). Similar notation will be used for the nonpositive (negative) case; that is, a
i
j
≤
0 (a
i
j
<
0) for all i
,
j
∈
N, and we will denote it by A
≤
0 (A
<
0).Now we recall some classes of matrices that we are working on.Definition 1.
Ann
×
n real matrix A
=
[
a
i
j
] is said to have a checkerboard pattern if sign
⁡
(
a
i
j
)
=
(
-
1
)
i
+
j or a
i
j
=
0 for all i
,
j
∈
N. When no entry is zero, one will say that A is strictly checkerboard.Definition 2.
A matrixA is said to be totally positive (negative) if all its minors of any order are positive (negative). That is, for every subset α
,
β
⊆
N, det
⁡
(
A
[
α
,
β
]
)
>
0 (det
⁡
(
A
[
α
,
β
]
)
<
0). It is denoted by TP (TN).Definition 3.
A matrixA is called totally nonpositive (nonnegative) if all its minors of any order are nonpositive (nonnegative). That is, for every subset α
,
β
⊆
N, det
⁡
(
A
[
α
,
β
]
)
≤
0 (det
⁡
(
A
[
α
,
β
]
)
≥
0). It is denoted by TNP (TNN).Definition 4.
Ann
×
n real matrix A is said to be a P-matrix if, for every subset α
⊆
N, det
⁡
(
A
[
α
]
)
>
0.Definition 5.
Ann
×
n real matrix A is called an M-matrix if A can be written as A
=
s
I
-
B, with B
≥
0 and s
≥
ρ
(
B
), where ρ
(
B
) denotes the spectral radius of matrix B, that is, the biggest absolute value of the eigenvalues of B.
For a matrixA, ℳ
(
A
) denotes its comparison matrix; that is,
(1)
ℳ
(
A
)
=
[
m
i
j
]
=
{
m
i
j
=
-
|
a
i
j
|
,
i
≠
j
m
i
i
=
|
a
i
i
|
.Definition 6.
Ann
×
n complex matrix A is called an H-matrix if its comparison matrix ℳ
(
A
) is an M-matrix.Note that nonsingularH-matrices having singular comparison matrix are included in this definition (see [7]).Remember that the Hadamard (or entrywise) product of twon
×
n matrices A
=
[
a
i
j
] and B
=
[
b
i
j
] is the matrix A
∘
B
=
[
a
i
j
b
i
j
].Definition 7.
The combined matrix of a nonsingular real matrixA is defined as C
(
A
)
=
A
∘
(
A
-
1
)
T. Then, if A
=
[
a
i
j
],
(2)
A
-
1
=
[
1
det
⁡
(
A
)
(
-
1
)
i
+
j
A
j
i
]
,
C
(
A
)
=
[
1
det
⁡
(
A
)
(
-
1
)
i
+
j
a
i
j
A
i
j
]
.
The elements of C
(
A
) will be denoted by c
i
j.It is clear that the combined matrix has the following properties: (i)C
(
A
T
)
=
C
(
A
-
1
) and (ii) C
(
A
) is doubly stochastic if C
(
A
) is nonnegative.


## 3. Matrices withC
(
A
)
≥
0

Looking at the definition of a combined matrix it is easy to see that the combined matrix of a triangular matrix is the identity matrix. Moreover, the following result from Lemma5.4
.
2
(
c
) (page 322) of [3] can be established.Lemma 8.
For any nonsingular matrixA, for any two permutation matrices P and Q, and for any triangular matrix T one has(i)
C
(
P
A
Q
)
=
P
C
(
A
)
Q,
(ii)
C
(
P
T
Q
)
=
P
C
(
T
)
Q
=
P
Q; that is, C
(
P
T
Q
) is a permutation matrix,
(iii)
C
(
P
T
P
T
)
=
I.From Definition7 one can observe that, for n
=
2 and n
=
3, C
(
A
)
=
I if and only if the matrix A is permutationally similar to a triangular matrix. The natural question is whether or not this is a general equivalence. As it is suggested in [3] (Problem 2, page 302) the equivalence is not true for some matrices with n
≥
4 as the following example shows.Example 9.
Consider the matrix(3)
A
=
[
a
0
0
a
b
c
0
b
0
d
e
0
0
d
e
f
]
a
,
b
,
c
,
d
,
e
,
f
≠
0
.
It is easy to compute C
(
A
) and to see that C
(
A
)
=
I. However, A is not permutationally similar to a triangular matrix since A is irreducible.Proposition 10.
LetA be a nonsingular matrix. If the combined matrix C
(
A
) is nonnegative and triangular, then C
(
A
)
=
I.Proof.
Recall thatC
(
A
) is doubly stochastic since it is nonnegative. Suppose C
(
A
) is upper triangular. In this case c
11
=
1 is the only positive entry of the first column and the first row. Reasoning as before with the other columns of A we conclude that C
(
A
)
=
I.A simple case to determine matrices having their combined matrixC
(
A
)
≥
0 is given for 2
×
2 matrices in the following result.Proposition 11.
LetA
=
[
a
i
j
] be a nonsingular 2
×
2 matrix. Then
(4)
C
(
A
)
≥
0
⟺
a
11
a
22
a
12
a
21
≤
0
.
In particular, (i) if a
11
a
22
=
0, then C
(
A
)
=
[
0
1
1
0
], (ii) if a
12
a
21
=
0, then C
(
A
)
=
I, and finally (iii) if a
11
a
22
a
12
a
21
<
0, then C
(
A
)
>
0.Proof.
Since(5)
A
=
[
a
11
a
12
a
21
a
22
]
,
(
A
-
1
)
T
=
1
det
⁡
(
A
)
[
a
22
-
a
21
-
a
12
a
11
]
then
(6)
C
(
A
)
=
1
det
⁡
(
A
)
[
a
11
a
22
-
a
21
a
12
-
a
21
a
12
a
11
a
22
]
.
(⇒) If C
(
A
)
≥
0, then a
11
a
22
/
det
⁡
(
A
)
≥
0 and -
(
a
21
a
12
/
det
⁡
(
A
)
)
≥
0. Therefore, (
a
11
a
22
)
(
a
12
a
21
)
≤
0.
(⇐) Suppose first that det
⁡
(
A
)
>
0. If a
11
a
22
<
0, since a
11
a
22
a
12
a
21
≤
0, then a
12
a
21
≥
0, in which case det
⁡
(
A
)
=
a
11
a
22
-
a
12
a
21
<
0. Then a
11
a
22
≥
0 and a
12
a
21
≤
0 and hence C
(
A
)
≥
0. Similarly, if det
⁡
(
A
)
<
0, we obtain a
11
a
22
≤
0 and a
12
a
21
≥
0 and then C
(
A
)
≥
0.
The two first particular cases come from the fact thatC
(
A
) is doubly stochastic, and the last case is because all entries are different from zero.Example 12.
Consider(7)
A
=
[
1
1
-
2
3
]
⟹
C
(
A
)
=
[
3
5
2
5
2
5
3
5
]
.
The positivity of the matrix may play an important role in our case. According to the definition of the combined matrix, we have the following.Theorem 13.
LetA
≥
0 (A
≤
0). Then C
(
A
)
≥
0 if and only if A
-
1
≥
0 (A
-
1
≤
0).Matrices with the property described in Theorem13 are necessarily nonnegative monomial matrices, as are the corresponding combined matrices. Monomial matrices are indeed permutationally similar to diagonal matrices and thus are orthogonal matrices. Below we prove a related result about a type of orthogonal matrices that was recently introduced in [8].Definition 14.
A nonsingular matrixA is called a G-matrix if two nonsingular diagonal matrices D
1 and D
2 exist such that (
A
-
1
)
T
=
D
1
A
D
2.Theorem 15.
LetA be a nonsingular G-matrix such that D
1
≥
0 and D
2
≥
0. Then, the combined matrix of A is nonnegative.Proof.
In this case, we have(8)
C
(
A
)
=
A
∘
(
A
-
1
)
T
=
A
∘
(
D
1
A
D
2
)
=
D
1
(
A
∘
A
)
D
2
which is nonnegative.Example 16.
The matrix(9)
A
=
[
2
1
1
-
1
]
is a G-matrix, since
(10)
(
A
-
1
)
T
=
[
1
3
1
3
1
3
-
2
3
]
is the result of D
A
D, where D
=
diag
⁡
(
1
/
6
,
2
/
3
). Then, the combined matrix is
(11)
C
(
A
)
=
[
2
3
1
3
1
3
2
3
]
≥
0
.It is well known that the combined matrix of anM-matrix is an M-matrix (see [3]). The following result gives the equivalent conditions to have a nonnegative combined matrix of an M-matrix.Theorem 17.
Let A be anM-matrix. Then, the following conditions are equivalent:(i)
C
(
A
)
≥
0,
(ii)
C
(
A
) is diagonal,
(iii)
C
(
A
)
=
I,
(iv)
a
i
i
A
i
i
=
1 for all i
∈
N.Proof.
SinceA is M-matrix, then A
-
1 is nonnegative and so the off-diagonal elements of C
(
A
) are nonpositive and the diagonal elements are positive. Then, C
(
A
)
≥
0 if and only if C
(
A
) is diagonal. The last two equivalences follow because the combined matrix is doubly stochastic.Despite the fact that the nonnegativity of the combined matrix of anM-matrix is reduced to the identity matrix, it is easy to find H-matrices for which its combined matrix is nonnegative and different from the identity matrix as the following example shows.Example 18.
The nonsingular matrices(12)
A
1
=
[
4
1
-
2
-
1
5
-
3
2
2
7
]
,
A
2
=
[
4
1
-
2
-
1
5
3
2
-
2
7
]
,
A
3
=
[
3
1
-
2
-
1
4
3
5
-
2
7
]
,
are H-matrices and each one has positive combined matrix:
(13)
C
(
A
1
)
=
1
189
[
164
1
24
11
160
18
14
28
147
]
,
C
(
A
2
)
=
1
193
[
164
13
16
3
160
30
26
20
147
]
,
C
(
A
3
)
=
1
160
[
102
22
36
3
124
33
55
14
91
]
.
It should be noted that A
3 is nonsingular but ℳ
(
A
3
) is a singular M-matrix.Now, we study the positivity of the combined matrix of totally positive and totally negative matrices.Theorem 19.
IfA is a TP-matrix, then C
(
A
) is strictly checkerboard. In addition, if A is a TN-matrix, then -
C
(
A
) is strictly checkerboard.Proof.
It is straightforward noting thatC
(
A
) is checkerboard in both cases.Then, the combined matrix of a TP-matrix or a TN-matrix is not nonnegative. However, we have the following result.Theorem 20.
IfA is a TP-matrix (TN-matrix), then S
C
(
A
)
S
>
0 (-
S
C
(
A
)
S
>
0), where S
=
diag
⁡
(
1
,
-
1,1
,
-
1
,
…
,
(
-
1
)
n
-
1
).To study the combined matrix of a TNN-matrix, we need some auxiliary results.Proposition 21 (see [9], Corollary 3.8).
IfA is a nonsingular TNN-matrix, then A is a P-matrix.Proposition 22.
IfA is a nonsingular TNN-matrix and a
i
j
≠
0 for some j
>
i, then a
i
,
j
-
1
≠
0.Proof.
Ifj
=
i
+
1, then a
i
,
j
-
1
=
a
i
i, which is positive since A is a P-matrix by Proposition 21. For j
≥
i
+
2, consider the submatrix
(14)
[
a
i
,
j
-
1
a
i
j
a
j
-
1
,
j
-
1
a
j
-
1
,
j
]
and let us work by contradiction. Suppose that a
i
,
j
-
1
=
0. Since A is a nonsingular TNN-matrix, then a
j
-
1
,
j
-
1
>
0 and a
i
j
>
0. Then
(15)
det
⁡
[
0
a
i
j
a
j
-
1
,
j
-
1
a
j
-
1
,
j
]
<
0
,
which is a contradiction.Proposition 23.
IfA is a nonsingular TNN-matrix, then the following conditions are equivalent:(i)
C
(
A
)
≥
0,
(ii)
a
i
j
A
i
j
=
0, i
+
j
=
2
k
+
1, k
∈
ℕ.Proof.
SinceA is TNN, a
i
j
≥
0 and A
i
j
≥
0 for all i
,
j. Then
(16)
c
i
j
=
1
det
⁡
(
A
)
(
-
1
)
i
+
j
a
i
j
A
i
j
{
≥
0
if
i
+
j
=
2
k
≤
0
if
i
+
j
=
2
k
+
1
.
Therefore, C
(
A
) is nonnegative if and only if a
i
j
A
i
j
=
0, when i
+
j
=
2
k
+
1.Proposition 24 (see [9], Theorem 3.3).
IfA is a nonsingular TNN-matrix, then S
A
-
1
S is also a nonsingular TNN-matrix, where S
=
diag
⁡
(
1
,
-
1
,
…
,
(
-
1
)
n
-
1
).Then we can establish the following result.Theorem 25.
LetA be a nonsingular TNN-matrix. Then the following conditions are equivalent:(i)
C
(
A
) is nonnegative,
(ii)
C
(
A
)
=
I.Proof.
(
ii
)
→
(
i
). If C
(
A
)
=
I, it is obvious that C
(
A
) is nonnegative.
(
i
)
→
(
ii
). Let us suppose that C
(
A
) is nonnegative. We note that a
i
j
A
i
j
=
0 whenever i
+
j
=
2
k
+
1, k
∈
ℕ, by Proposition 23. Then it remains to prove that a
i
j
A
i
j
=
0 whenever i
+
j
=
2
k and i
≠
j. We work by contradiction. For this, we suppose that there exists a
i
j
A
i
j
≠
0 with i
+
j
=
2
k and i
<
j. By Proposition 24  S
(
A
-
1
)
T
S is a nonsingular TNN-matrix. Applying Proposition 22 to both A and S
(
A
-
1
)
T
S we have that a
i
,
j
-
1
≠
0 and A
i
,
j
-
1
≠
0. Therefore, a
i
,
j
-
1
A
i
,
j
-
1
≠
0, with i
+
(
j
-
1
)
=
2
k
-
1, and this contradicts the result of Proposition 23. Thus, when i
<
j, we have that a
i
j
A
i
j
=
0. Then, C
(
A
) is a lower triangular and nonnegative matrix. Hence, C
(
A
)
=
I by Proposition 10.Now, let us figure out the combined matrix of a TNP-matrix. Since all minors of TNP-matrices are nonpositive, it is clear that the combined matrix of a nonsingular TNP-matrix is not, in general, nonnegative. In fact, we have this simple result.Theorem 26.
LetA be a nonsingular TNP-matrix. Then C
(
A
) is nonnegative if and only if a
i
j
A
i
j
=
0, whenever i
+
j
=
2
k, k
∈
ℕ.However, there exist TNP-matrices with nonnegative combined matrices as the following example shows.Example 27.
Consider the totally nonpositive matrix(17)
A
=
[
0
-
1
-
1
0
]
.
The combined matrix is
(18)
C
(
A
)
=
[
0
1
1
0
]
,
which is nonnegative.The question now is to know whether or not there are more TNP-matrices with nonnegative combined matrices. As we see below, only TNP-matrices of size2
×
2 may have this property. To prove this we need some auxiliary results concerning TNP-matrices.Proposition 28.
LetA be an n
×
n nonsingular TNP-matrix with n
≥
3. If there exists an index j
≥
2 such that A
1
j
≠
0, then A
1
,
j
-
1
≠
0.Proof.
Suppose by contradiction that there is anA
1
j
≠
0 and A
1
,
j
-
1
=
0 for some j
≥
2. Since A
-
1 is nonsingular, there exists an index t
>
1 such that A
t
,
j
-
1
≠
0 and then
(19)
det
⁡
[
A
1
,
j
-
1
A
1
j
A
t
,
j
-
1
A
t
j
]
<
0
,
which is a contradiction with the signature (
1,1
,
…
,
1
,
-
1
) of the matrix S
A
-
1
S (see [10]).Corollary 29.
LetA be an n
×
n nonsingular TNP-matrix with n
≥
3.(i)
IfA
1
j
≠
0 for some j
≥
2, then A
1
t
≠
0 for all t
≤
j.
(ii)
Ifc
1
j
≠
0 for some j
≥
2, then c
1
t
≠
0, 2
≤
t
≤
j.Proof.
(i) The proof follows from Proposition28.
(ii) SinceA is TNP, a
1
t
≠
0 for all t
≥
2 (see [11], Theorem 2.1 (i)). Then, using part (i) of this corollary, we conclude that c
1
t
=
a
1
t
A
1
t
≠
0 whenever 2
≤
t
≤
j.In the following theorem we show how the first row and the second column of a nonnegative combined matrix of a TNP-matrix are.Theorem 30.
LetA be an n
×
n nonsingular TNP-matrix with n
≥
3. If C
(
A
) is nonnegative, then the first row of C
(
A
) is (
0,1
,
0
,
…
,
0
) and the second column is (
1,0
,
…
,
0
)
T.Proof.
Again, sinceA is TNP, a
1
t
≠
0 for all t
≥
2. Furthermore, A
13
=
A
15
=
⋯
=
A
1,2
k
+
1
=
0, k
∈
ℕ, k
≤
(
n
-
1
)
/
2 by Theorem 26 and A
1
j
=
0 for j
=
3,4
,
…
,
n by Proposition 28. Then, the proof follows since C
(
A
) is doubly stochastic and c
11
=
0.Now, we can give the main theorem on combined matrices of TNP-matrices; that is, we are going to prove that there does not exist any nonsingular TNP-matrixA of size n
≥
3 such that its combined matrix is nonnegative.Theorem 31.
LetA be an n
×
n nonsingular TNP-matrix with n
≥
3. Then C
(
A
) is not nonnegative.Proof.
Let us work by contradiction and suppose that there exists a nonsingular TNP-matrixA of size k
×
k, with k
≥
3 and C
(
A
)
≥
0. By Theorem 30 we know the structure of the first row and the second column of C
(
A
). Let us focus on its first column where its first entry is c
11
=
0. Since C
(
A
) is nonnegative and so doubly stochastic, then there must exist an index t
>
1 such that c
t
1
≠
0, and then A
t
1
≠
0. Further, by Theorem 30 and Theorem 2.1 (i) of [11] A
t
2
=
0 and A
12
≠
0 by Theorem 30. Then
(20)
det
⁡
[
A
11
A
12
A
t
1
A
t
2
]
<
0
.
This is a contradiction with signature of S
A
-
1
S according to [10].Finally, we prove what kind of totally nonpositive matrices of sizen
=
2 have their combined matrix nonnegative in the following result.Theorem 32.
Let the2
×
2 TNP-matrix be
(21)
A
=
[
-
a
-
b
-
c
-
d
]
,
where a, b, c, d are nonnegative. Then C
(
A
)
≥
0 if and only if at least one of the entries a or d is zero. In this case, C
(
A
)
=
[
0
1
1
0
].Proof.
The computation of the combined matrix gives(22)
C
(
A
)
=
1
det
⁡
A
[
a
d
-
c
b
-
c
b
a
d
]
.
Then, since det
⁡
A
<
0, C
(
A
)
≥
0 if and only if a
d
=
0. In this case, det
⁡
A
=
-
b
c and C
(
A
)
=
[
0
1
1
0
].In brief, only2
×
2 antitriangular TNP-matrices have their combined matrix nonnegative.



---

*Source: 182354-2014-04-07.xml*