Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

There are some classes of structured matrices very important in applications and that also present many advantages under a mathematical and a computational point of view. In this last aspect, we can mention that recent research in Numerical Linear Algebra has shown that certain classes of matrices allow us to perform many computations to high relative accuracy, independently of the size of the condition number (cf. [14]). For instance, the computation of their singular values, eigenvalues or inverses. These classes of matrices are defined by special sign or other structure and require to know some natural parameters to high relative accuracy, and they are related to some subclasses of P-matrices. Let us recall that a square matrix is called a P-matrix if all its principal minors are positive. Subclasses of P-matrices with many applications are the nonsingular totally nonnegative matrices and the nonsingular M-matrices (a nonsingular matrix A with nonpositive off-diagonal entries is an M-matrix if A −1 has nonnegative entries). Usually, accurate spectral computation (eigenvalues, singular values) or accurate inversion is assured when an accurate matrix factorization with a suitable pivoting is provided. For instance, the bidiagonal decomposition in the case of totally positive matrices (see [24]) or an LDU factorization after a symmetric pivoting in the case of diagonally dominant matrices (cf. [12, 29]).

Let us recall that a matrix is totally positive (TP) if all its minors are nonnegative. Let us remind that TP matrices are also called in the literature totally nonnegative matrices (cf. [17]). The class of totally positive matrices is representative of the properties mentioned in the first sentence of this introduction. It has applications to many fields, presents interesting theoretical properties and has very nice stability and computational properties (see [2, 17–19, 22, 24, 28, 31]).

In this paper, we survey the extension of some properties valid for TP matrices to a more general class of matrices, called SBD matrices (matrices with signed bidiagonal decomposition). We also extend the affirmative answer of an inequality conjectured for the Frobenius norm of the inverse of matrices whose entries belong to [0, 1] to the class of nonsingular TP matrices. In Sect. 2 we present the class of SBD matrices and several results extending properties of TP matrices to the new class (see also [7]). In Sect. 3 we introduce the basic concepts related to the conjecture. We start with the case of tridiagonal TP matrices and provide a proof using elementary arguments for the sake of self completeness. In Sect. 4 we prove the extension to any class of P-matrices closed under Schur complements and satisfying the Fisher inequality. As a consequence, we derive the result for nonsingular TP matrices.

2 A Class of Matrices Related to Total Positivity

Let Q k, n be the set of sequences of k ( ≤ n) positive integers less than or equal to n. Given α ∈ Q k, n and β ∈ Q l, n we denote by A[α | β] the k × l submatrix of A containing rows numbered by α and columns numbered by β. If α = β then we denote the principal submatrix by A[α]: = A[α | α]. We use α c to denote the increasingly rearranged complement of α, α c = { 1, …, n}∖ α. Besides we denote A(α | β]: = A[α c | β], A[α | β): = A[α | β c] and A(α): = A[α c].

Some classes of matrices, including TP matrices, can be decomposed as a product of bidiagonal matrices. These decompositions use matrices of the form

$$\displaystyle{L^{(k)} = \left (\begin{array}{*{10}c} 1& & & & & &\\ 0 &1 & & & &&\\ & \ddots & \ddots & & && \\ & &0& 1 & & & \\ & & &l_{n-k}^{(k)} & 1& &\\ & & & & \ddots & \ddots& \\ & & & & &l_{n-1}^{(k)} & 1 \end{array} \right ),}$$
$$\displaystyle{U^{(k)} = \left (\begin{array}{*{10}c} 1&0& & & & &\\ & \ddots & \ddots & & &&\\ & &1 &0 & && \\ & & &1&u_{n-k}^{(k)} & &\\ & & & & \ddots & \ddots& \\ & & & & & 1&u_{n-1}^{(k)} \\ & & & & & & 1 \end{array} \right ),}$$

where \(k = 1,\ldots,n - 1\).

Let A be a nonsingular n × n matrix. Suppose that we can write A as a product of bidiagonal matrices

$$\displaystyle{ A = L^{(1)}\cdots L^{(n-1)}DU^{(n-1)}\cdots U^{(1)}, }$$
(1)

where D = diag(d 1, …, d n ), and, for \(k = 1,\ldots,n - 1\), L (k) and U (k) are matrices as mentioned above satisfying:

  1. 1.

    d i ≠ 0 for all i,

  2. 2.

    \(l_{i}^{(k)} = u_{i}^{(k)} = 0\) for i < n − k,

  3. 3.

    \(l_{i}^{(k)} = 0 \Rightarrow l_{i+s}^{(k-s)} = 0\) for \(s = 1,\ldots,k - 1\) and\(u_{i}^{(k)} = 0 \Rightarrow u_{i+s}^{(k-s)} = 0\) for \(s = 1,\ldots,k - 1\).

Then we denote (1) by \(\mathcal{B}\mathcal{D}(A)\) a bidiagonal decomposition of A. It was proved, in [4, Proposition 2.2], that this decomposition is unique.

Let us recall an important result that characterizes nonsingular TP matrices in terms of it bidiagonal decomposition (it is a consequence of Theorem 4.2 of [20]).

Theorem 1

A nonsingular n × n matrix A is TP if and only if there exists a (unique) \(\mathcal{B}\mathcal{D}(A)\) such that:

  1. 1.

    d i > 0 for all i.

  2. 2.

    l i (k) ≥ 0, u i (k) ≥ 0 for 1 ≤ k ≤ n − 1 and \(n - k \leq i \leq n - 1\) .

Let us now define a class of matrices with bidiagonal decomposition with special sign conditions on the entries of bidiagonal matrices. This class will generalize the class of nonsingular TP matrices. Recall that a vector ɛ = (ɛ 1, …, ɛ m ) with ɛ j  ∈ {−1, 1} for j = 1, …, m is called signature.

Definition 1

Given a signature \(\varepsilon = (\varepsilon _{1},\ldots,\varepsilon _{n-1})\) and a nonsingular n × n matrix A, we say that A is SBD with signature ɛ if there exists a \(\mathcal{B}\mathcal{D}(A)\) such that:

  1. 1.

    d i  > 0 for all i,

  2. 2.

    l i (k) ɛ i  ≥ 0, u i (k) ɛ i  ≥ 0 for 1 ≤ k ≤ n − 1 and \(n - k \leq i \leq n - 1\).

We say that A is SBD, if it is SBD with some signature ɛ. Observe that these matrices are nonsingular.

Given a signature \(\varepsilon = (\varepsilon _{1},\ldots,\varepsilon _{n-1})\), let us define a diagonal matrix K = diag(k 1, …, k n ) with k i satisfying

$$\displaystyle{ k_{i} \in \{-1,1\}\;\forall \,i = 1,\ldots,n,\quad k_{i}k_{i+1} =\varepsilon _{i}\;\forall \,i = 1,\ldots,n - 1. }$$
(2)

Now, we present three results that provide characterizations of SBD matrices. Some of these characterizations are given in terms of important matrices decompositions, such as LDU decomposition or UL decomposition.

The following theorem appeared in [4, Theorem 3.1] and provides several characterizations of SBD matrices.

Theorem 2

Let A = (a ij ) 1≤i,j≤n be a nonsingular matrix and let \(\varepsilon = (\varepsilon _{1},\ldots,\varepsilon _{n-1})\) be a signature. Then the following properties are equivalent:

  1. (i)

    A is SBD with signature ɛ.

  2. (ii)

    KAK = |A| is TP, where K is any diagonal matrix satisfying (2).

  3. (iii)

    A −1 is SBD with signature \(-\varepsilon = (-\varepsilon _{1},\ldots,-\varepsilon _{n-1})\) .

  4. (iv)

    |A| is TP and, for all 1 ≤ i,j ≤ n,

    $$\displaystyle{sign(a_{ij}) = \left \{\begin{array}{l} \varepsilon _{j}\cdots \varepsilon _{i-1},\mbox{ if }i> j \\ 1\qquad \quad,\mbox{ if }i = j \\ \varepsilon _{i}\cdots \varepsilon _{j-1},\mbox{ if }i <j.\end{array} \right.}$$

Observe that an SBD matrix with signature (1, …, 1) is a nonsingular TP matrix. As a corollary of Theorem 2 we have the following result, which corresponds with [4, Corollary 3.3]:

Corollary 1

Let A be a nonsingular matrix. Then the following properties are equivalent:

  1. (i)

    A is SBD with signature (1,…,1).

  2. (ii)

    A is TP.

  3. (iii)

    A −1 is SBD with signature \((-1,\ldots,-1)\) .

Let us now present a characterization of SBD matrices in terms of their LDU decomposition (cf. [4, Proposition 3.5]).

Proposition 1

An n × n matrix A is SBD with signature \(\varepsilon = (\varepsilon _{1},\ldots,\varepsilon _{n-1})\) if and only if A = LDU, where L (resp., U) is a lower (resp., an upper) triangular matrix with unit diagonal and SBD with signature ɛ and D is a diagonal matrix whose diagonal entries are positive.

Let us recall that, given a matrix A, a factorization A = BC is called an UL decomposition if B is upper triangular and C is lower triangular. In order to characterize SBD matrices in terms of their UL decomposition, we need to introduce a new class of matrices (presented in [5]). We say that a matrix A is signature similar to TP with signature ɛ, denoted by SSTP with signature ɛ, if A = KBK, where B is TP and K satisfies (2). The following proposition (which corresponds with [5, Proposition 3.10]) gives a characterization of SBD matrices by their UL decomposition.

Proposition 2

A matrix A is SBD with signature ɛ if and only if there exists a lower and an upper triangular SSTP matrices with signature ɛ, A L and A U , such that A = A U A L .

An algorithm can be performed with high relative accuracy if it does not include subtractions (except of the initial data), that is, if it only includes products, divisions, sums of numbers of the same sign and subtractions of the initial data (cf. [14]). Up to now, we only have algorithms with high relative accuracy for a reduced number of classes of matrices, related with total positivity (cf. [1, 10, 11, 24, 26]) or diagonal dominance (cf. [12, 29]). In the problem of finding algorithms with high relative accuracy, the choice of adequate parameters is crucial to avoid subtractions during the algorithm. For nonsingular TP matrices, if we know with high relative accuracy the entries of (1), then algorithms with high relative accuracy can be applied (cf. [23, 24]). We recall that, with the same parameters, these algorithms can be used to compute with high relative accuracy the singular values, eigenvalues, inverses or the LDU decomposition of SBD matrices (cf. [4]).

Given an SBD matrix A, let us observe that, from (1) and taking into account that K 2 = I, we have

$$\displaystyle\begin{array}{rcl} KAK& =& (KL^{(1)}K)\cdots (KL^{(n-1)}K)(KDK) \\ & & (KU^{(n-1)}K)\cdots (KU^{(1)}K), {}\end{array}$$
(3)

which is the \(\mathcal{B}\mathcal{D}(KAK)\). Besides, taking into account (2), it can be checked that all factors of \(\mathcal{B}\mathcal{D}(KAK)\) are nonnegative.

As shown in recent references [13, 15, 23–26], the diagonal entries of the diagonal matrix D of the \(\mathcal{B}\mathcal{D}(A)\) (see Eq. (1)) and the off-diagonal entries of the remaining factors of (1) can be considered natural parameters associated with A. In the computation of these parameters, Neville elimination (see [26]) has been frequently a useful tool. Let us see that if we assume that we know these parameters with high relative accuracy for SBD matrices, then we can find algorithms with high relative accuracy to compute their singular values, their eigenvalues, their inverses or to solve certain linear systems Ax = b (those with Kb with a chessboard pattern of signs).

For all the mentioned computations we can follow a procedure that were presented in [4] and it can be summarized by the following steps:

  1. 1.

    From \(\mathcal{B}\mathcal{D}(A)\), we obtain \(\mathcal{B}\mathcal{D}(\vert A\vert )\), given by (3).

  2. 2.

    We can apply known algorithms with high relative accuracy for TP matrices to \(\mathcal{B}\mathcal{D}(\vert A\vert )\). Recall that, by Theorem 2, | A | is TP if A is SBD.

  3. 3.

    From the information obtained for | A | , we can get the corresponding result for A.

Let us now explain how to perform each of the previous steps.

As for Step 1, let us assume that we know the \(\mathcal{B}\mathcal{D}(A)\) (see Eq. (1)) with high relative accuracy for a given SBD matrix. Then | A | = KAK for a diagonal matrix K satisfying (2) and so we can deduce from (3) that

$$\displaystyle{ \vert A\vert = \vert L^{(1)}\vert \cdots \vert L^{(n-1)}\vert \vert D\vert \vert U^{(n-1)}\vert \cdots \vert U^{(1)}\vert }$$
(4)

is the \(\mathcal{B}\mathcal{D}(\vert A\vert )\). Since all factors of \(\mathcal{B}\mathcal{D}(KAK)\) are nonnegative, we have that | L ( j) | = KL ( j) K, | U ( j) | = KU ( j) K for all \(j = 1,\ldots,n - 1\). Thus, (4) follows from (3).

As for Step 2, we apply the corresponding algorithm for TP matrices with high relative accuracy, using \(\mathcal{B}\mathcal{D}(\vert A\vert )\) (given by (4)). In particular, we consider the following accurate computations with TP matrices:

  1. A.

    The eigenvalues of | A | can be obtained by the method of [23, Sect. 5].

  2. B.

    The singular values of | A | can be obtained by the method of [23, Sect. 6].

  3. C.

    The inverse of | A | can be obtained by the method of [24, p. 736].

  4. D.

    Observe that Ax = b is equivalent to solving (KAK)(Kx) = Kb, that is, | A | (Kx) = Kb. Then, | A | −1 can be calculated accurately by the procedure of the previous case. By Ando [2, Theorem 3.3], | A | −1 has a chessboard pattern of signs and so, since Kb has also a chessboard pattern of signs, \(Kx = \vert A\vert ^{-1}(Kb)\) can be calculated without subtractions and therefore with high relative accuracy.

As for Step 3, we have the following cases corresponding to each of the cases of Step 2:

  1. A.

    We have that \(\vert A\vert = KAK = K^{-1}AK\) and so they are similar matrices and have the same eigenvalues.

  2. B.

    The singular values of A and | A | coincide because | A | = KAK, that is, | A | and A coincide up to unitary matrices.

  3. C.

    We have that \(\vert A\vert ^{-1} = (KAK)^{-1} = KA^{-1}K\) and so \(A^{-1} = K\vert A\vert ^{-1}K\).

  4. D.

    If we know Kx, then x = K(Kx).

In addition, let us show that if we have the \(\mathcal{B}\mathcal{D}(A)\) (see Eq. (1)) with high relative accuracy, then we can also calculate the LDU decomposition of A with high relative accuracy, and even obtain the matrix A with high relative accuracy. In fact, by the uniqueness of the LDU decomposition of a matrix, it can be checked that

$$\displaystyle{ L = L^{(1)}\cdots L^{(n-1)},\qquad U = U^{(n-1)}\cdots U^{(1)}. }$$
(5)

Since the bidiagonal matrices L (k), U (k) satisfy sign properties of Definition 1, then we have that matrices L and U can be calculated without subtractions and so with high relative accuracy. Then we can also compute A = LDU with high relative accuracy.

Several properties of SBD matrices have been studied in [3, 4]. We summarize some of them in the following result.

Proposition 3

Let A,B be two n × n SBD matrices with the same signature ɛ. Then

  1. (i)

    A T is also SBD with signature ɛ.

  2. (ii)

    Any principal submatrix of A is SBD.

  3. (iii)

    AB is also SBD with signature ɛ.

  4. (iv)

    A is a P-matrix, that is, it has all its principal minors positive.

Given two matrices A = (a ij )1 ≤ i, j ≤ n and B = (b ij )1 ≤ i, j ≤ n , we define the Hadamard product, or entrywise product, of A and B as the matrix A ∘ B: = (a ij b ij )1 ≤ i, j ≤ n . The Hadamard core (cf. [5, 9]) of the n × n TP matrices is given by

$$\displaystyle{ CTP:=\{ A: B\mbox{ is TP } \Rightarrow A \circ B\mbox{ is TP}\}. }$$
(6)

It is known, by Fallat and Johnson [17, Theorem 8.2.5], that tridiagonal TP matrices are in the CTP. Then, by Fallat and Johnson [17, Corollary 8.3.2], it can be deduced the following result (cf. [5, Proposition 3.1]).

Proposition 4

Let A be an n × n tridiagonal TP matrix and B an n × n TP matrix. Then det (A ∘ B) ≥ det Adet B.

Given an n × n TP matrix A, then we say that A is oscillatory if a certain power of A, A k, becomes strictly totally positive; that is, all the minors of A k are strictly positive (see [2]). Recall that, by Ando [2, Theorem 4.2], a nonsingular TP matrix A = (a ij )1 ≤ i, j ≤ n is oscillatory if and only if a i, i+1 > 0 and a i+1, i  > 0 for all \(i = 1,\ldots,n - 1\). Moreover, observe that since an oscillatory matrix is TP and nonsingular, we have that a ii  > 0 for all i = 1, …, n (cf. [2, Corollary 3.8]). Thus, a tridiagonal oscillatory matrix A = (a ij )1 ≤ i, j ≤ n satisfies a ij ≠ 0 for | i − j | ≤ 1.

It is known (cf. [31, Proposition 4.12], [9, Corollary 2.7] or [17, Corollary 8.2.6]) that the Hadamard product of two n × n tridiagonal TP matrices is again a tridiagonal TP matrix. Taking into account that the nonsingularity of tridiagonal TP matrices is also preserved by the Hadamard product (see Proposition 4), we can extend the previous fact to nonsingular tridiagonal TP matrices. Thus, in [5, Proposition 3.2], a generalization of [27, Theorem 1] from the class of tridiagonal oscillatory matrices to the class of nonsingular tridiagonal TP matrices was given.

Proposition 5

Let A,B be two nonsingular n × n tridiagonal TP matrices. Then A ∘ B is a nonsingular tridiagonal TP matrix.

We shall now extend Proposition 4 to the class of SBD matrices. Analogously to (6), we define the Hadamard core of the n × n SBD matrices by

$$\displaystyle{ CSBD:=\{ A: B\mbox{ is SBD } \Rightarrow A \circ B\mbox{ is SBD}\}. }$$
(7)

The following result (cf. [5, Proposition 3.4]) shows that tridiagonal SBD matrices belong to CSBD.

Proposition 6

Let A be an n × n tridiagonal SBD matrix and B an n × n SBD matrix. Then A ∘ B is SBD.

The set of tridiagonal SBD matrices form a semigroup with respect to the Hadamard product as the following corollary [5, Corollary 3.5] shows. It extends Proposition 5 to tridiagonal SBD matrices and it is a direct consequence of Proposition 6.

Corollary 2

Let A,B be two n × n tridiagonal SBD matrices. Then the matrix A ∘ B is a tridiagonal SBD matrix.

Besides, Corollary 2 cannot be extended to SBD matrices that are not tridiagonal, as the following example shows. Observe that the following matrix is a nonsingular TP matrix

$$\displaystyle{A = \left (\begin{array}{*{10}c} 1.1&1& 1\\ 1 &1 & 1 \\ 0 &1&1.1 \end{array} \right ),}$$

so, by Theorem 2, A is SBD. However, the matrix

$$\displaystyle{A\circ A^{T} = \left (\begin{array}{*{10}c} 1.1^{2} & 1& 0 \\ 1 &1& 1 \\ 0 &1&1.1^{2} \end{array} \right )}$$

satisfies that \(\det (A \circ A^{T}) = -0.9559 <0\). So A ∘ A T is not a P-matrix. Recall that, by Proposition 3, SBD matrices are P-matrices, and then, we conclude that A ∘ A T it is not SBD.

Let us recall that given A an n × n matrix, if A[α∣β] is invertible for some α, β ∈ Q k, n , 1 ≤ k ≤ n, then the Schur complement of A[α∣β] in A, denoted by A∕A[α∣β], is defined as

$$\displaystyle{ A/A[\alpha \mid \beta ]:= A(\alpha \mid \beta ) - A(\alpha \mid \beta ]A[\alpha \mid \beta ]^{-1}A[\alpha \mid \beta ). }$$
(8)

If α = β, we denote A∕A[α∣α] by A∕A[α].

If A is invertible, we can use formula (1.29) of [2] to derive the following formula for Schur complement of principal submatrices:

$$\displaystyle{ (A/A[\alpha ])^{-1} = A^{-1}(\alpha ) = A^{-1}[\alpha ^{c}]. }$$
(9)

In [17, Proposition 1.5.1], it is shown that the Schur complement of principal submatrices using contiguous index sets, A∕A[α] with \(\alpha = (i,i + 1,\ldots,i + k - 1)\), of a nonsingular TP matrix, is TP. However, this result is not valid for general Schur complements of TP matrices. For SBD matrices, in [5, Theorem 3.6] it was proved that general Schur complements of principal submatrices of SBD matrices are again SBD.

Theorem 3

Let A be an SBD matrix. Then A∕A[α], the Schur complement of A[α] in A, is SBD for all α ∈ Q k,n , 1 ≤ k ≤ n.

Finally, let us present a lower bound for a minimal eigenvalue of an SBD matrix. Let us recall that the well-known Gerschgorin’s Circles Theorem provides a lower bound for an eigenvalue with minimal absolute value, λ ∗, of a matrix A = (a ij )1 ≤ i, j ≤ n :

$$\displaystyle{\vert \lambda _{{\ast}}\vert \geq \min _{i}\left \{\vert a_{ii}\vert -\sum _{j\neq i}\vert a_{ij}\vert \right \}.}$$

The following result improves this bound for SBD matrices. The next index subset is used in following result: given i ∈ { 1, …, n} let

$$\displaystyle{ J_{i}:=\{\, j\vert \,\vert j - i\vert \mbox{ is odd}\}. }$$
(10)

Observe that, by Theorem 2, we know that K | A | K is SBD, where | A | is a TP matrix; that is, SBD matrices are similar to TP matrices. So A and | A | have the same eigenvalues. Recall that an eigenvalue with minimal absolute value of a nonsingular TP matrix is positive (cf. [2, Corollary 6.6]). Thus, we know that SBD matrices also satisfy this property. The following result extends to SBD matrices the bound obtained in [30, Theorem 4.4] for nonsingular TP matrices and corresponds with [5, Corollary 2.7].

Proposition 7

Let A be an n × n SBD matrix and let λ ∗ be an eigenvalue of A with minimal absolute value. For each i ∈{ 1,…,n}, let J i be the index subset defined by (10). Then

$$\displaystyle{ \lambda _{{\ast}}\geq \min _{i}\left \{a_{ii} -\sum _{j\in J_{i}}\vert a_{ij}\vert \right \}. }$$
(11)

The following example (which is included in [5, Example 2.8]) shows that the bound given by Proposition 7 cannot be improved.

Example 1

Let us consider the SBD matrix

$$\displaystyle{A = \left (\begin{array}{*{10}c} 12&-7&-1\\ 0 & 6 & 1 \\ 0 & 3 & 8 \end{array} \right ).}$$

The eigenvalues of A are 12, 9 and 5, which coincides with the eigenvalues of the TP matrix | A | . Observe that the bound given by (11), λ ∗ ≥ 5, cannot be improved, because this bound is achieved by the smallest eigenvalue. Observe also that the lower bound given by the Gerschgorin’s Circles Theorem is λ ∗ ≥ min{4, 5, 5} = 4, which is worse than the previous one.

3 Inequality for Tridiagonal TP Matrices

We present in this section another property of tridiagonal TP matrices. In particular, a lower bound for the norm of the inverse of a tridiagonal TP matrix with entries in [0, 1] is presented.

Recall that, given a nonsingular n × n matrix A, the procedure of Gaussian elimination without pivoting provides as result a sequence of n − 1 matrices:

$$\displaystyle{ A = A^{(1)}\longrightarrow A^{(2)}\longrightarrow \cdots \longrightarrow A^{(n)}, }$$
(12)

where A (t) has zeros below its main diagonal in the first t − 1 columns:

$$\displaystyle{A^{(t)} = \left (\begin{array}{*{10}c} a_{11}^{(t)} & a_{12}^{(t)} & \ldots & \ldots & \ldots & \ldots & a_{1n}^{(t)} \\ 0 &a_{22}^{(t)} & \ldots & \ldots & \ldots & \ldots & a_{2n}^{(t)} \\ \vdots & 0 &\ddots& & & & \vdots\\ \vdots & \vdots & &\ddots & & &\vdots \\ \vdots & \vdots & & & a_{tt}^{(t)} & \ldots & a_{tn}^{(t)}\\ \vdots & \vdots & & & \vdots & & \vdots \\ 0 & 0 &\ldots &\ldots &a_{nt}^{(t)} & \ldots & a_{nn}^{(t)}\\ \end{array} \right ).}$$

Given a real matrix A = (a ij )1 ≤ i, j ≤ n its Frobenius norm is defined as

$$\displaystyle{\|A\|_{F}:= \left (\sum _{i=1}^{n}\sum _{ j=1}^{n}a_{ ij}^{2}\right )^{1/2}.}$$

A Hadamard matrix of order n is a matrix A = (a ij )1 ≤ i, j ≤ n such that a ij  ∈ {−1, 1} whose rows and columns are mutually orthogonal; that is, AA T = nI n , where I n is the identity matrix of order n. An S-matrix of order n is a matrix A = (a ij )1 ≤ i, j ≤ n such that a ij  ∈ { 0, 1}, formed by considering a Hadamard matrix of order n + 1 in which the entries in the first row and column are 1, changing 1’s to 0’s and − 1’s to 1’s, and deleting the first row and the first column.

Let \(\mathcal{D}_{n}\) denote the set of all n × n matrices A whose entries are in the interval [0, 1]. Sloane and Harwit proposed (see [32]) the following conjecture concerning matrices in \(\mathcal{D}_{n}\).

Conjecture 1

If \(A \in \mathcal{D}_{n}\) is a nonsingular matrix, then

$$\displaystyle{\|A^{-1}\|_{ F} \geq \frac{2n} {n + 1},}$$

where the equality holds if and only if A is an S-matrix.

This conjecture appeared from a problem in the field of spectroscopy (cf. [21]). The conjecture were proved for matrices of odd order by Cheng in 1987 (see [8, 16]).

We now present a result that proves the conjecture for nonsingular tridiagonal TP matrices that lie in the set \(\mathcal{D}_{n}\).

Proposition 8

Let \(A \in \mathcal{D}_{n}\) be a nonsingular tridiagonal TP matrix. Then

$$\displaystyle{\|A^{-1}\|_{ F} \geq \frac{2n} {n + 1}.}$$

Proof

We proceed by induction on n. If n = 2 it is known (see [16]) that \(\|A^{-1}\|_{F} \geq \sqrt{2}> 4/3\).

Suppose that the result holds for matrices of order n − 1; that is, given \(\tilde{A} \in \mathcal{D}_{n-1}\) nonsingular tridiagonal TP, then \(\|\tilde{A}^{-1}\|_{F} \geq \frac{2n-2} {n}\). Consider now \(A \in \mathcal{D}_{n}\) a nonsingular tridiagonal TP matrix. Since, by Ando [2, Corollary 3.8], a nonsingular TP matrix have positive principal minors, we have that a 11 > 0. Then, after the first step in Gaussian elimination, we have A (2) = (a ij (2))1 ≤ i, j ≤ n (see Eq. (12))

$$\displaystyle{A^{(2)} = \left (\begin{array}{c|ccc} a_{11} & a_{12} & & \\ \hline 0& & & \\ \vdots & &A^{(2)}[2,\ldots,n]& \\ 0 & & & \end{array} \right )}$$

where a i1 (2) = 0 for all i ∈ { 2, …, n} and a 11 (2) = a 11 ≠ 0. Observe that we can express \(A = L_{1}^{-1}A^{(2)}\) ( = : (a ij )1 ≤ i, j ≤ n ), where

$$\displaystyle{L_{1} = \left (\begin{array}{*{10}c} 1 & & & & \\ \frac{-a_{21}} {a_{11}} & 1& & & \\ 0 & &1& &\\ \vdots & & &\ddots&\\ 0 & & &&1 \end{array} \right ).}$$

Thus, we have that

$$\displaystyle\begin{array}{rcl} A^{-1}& =& (L_{ 1}^{-1}A^{(2)})^{-1} = (A^{(2)})^{-1}L_{ 1} \\ & =& \left (\begin{array}{c|ccc} \frac{1} {a_{11}} & \beta _{2} & \cdots &\beta _{n} \\ \hline 0& & & \\ \vdots & &(A^{(2)}[2,\ldots,n])^{-1} & \\ 0 & & & \end{array} \right )\left (\begin{array}{*{10}c} 1 & & & \\ \frac{-a_{21}} {a_{11}} & 1& &\\ & &\ddots& \\ & & &1 \end{array} \right ) \\ & =& \left (\begin{array}{c|ccc} (A^{-1})_{11} & \beta _{2} & \cdots &\beta _{n} \\ \hline \gamma _{2} & & & \\ \vdots & & (A^{(2)}[2,\ldots,n])^{-1} & \\ \gamma _{ n} & & & \end{array} \right ) {}\end{array}$$
(13)

where β i , γ i are real numbers for all i ∈ { 2, …, n} and (A −1)11 denotes the (1,1) entry of A −1. Since A (2) is nonsingular we have that B: = A (2)[2, …, n] is also nonsingular. Taking into account that \(A \in \mathcal{D}_{n}\) is tridiagonal TP and considering Gaussian elimination, we have that

$$\displaystyle{a_{ij}^{(2)} = a_{ ij} \in [0,1]}$$

for all i, j ∈ { 2, …, n}, (i, j) ≠ (2, 2) and we deduce that

$$\displaystyle{a_{22}^{(2)} = a_{ 22} -\frac{a_{21}} {a_{11}}a_{12} \leq a_{22} \leq 1}$$

and

$$\displaystyle{a_{22}^{(2)} = a_{ 22} -\frac{a_{21}} {a_{11}}a_{12} = \frac{\det A[1,2\vert 1,2]} {a_{11}}> 0.}$$

Thus \(B \in \mathcal{D}_{n-1}\). Furthermore, observe that B is also tridiagonal and it can be expressed as the Schur complement \(B = A/A[1]\) and this Schur complement in a TP matrix is TP (see [2, Theorem 3.3]). Thus, by the induction hypothesis, we have that

$$\displaystyle{ \|B^{-1}\|_{ F} \geq \frac{2n - 2} {n}. }$$
(14)

Observe that, since \(A \in \mathcal{D}_{n}\) is TP and considering the (1,1) cofactor of A and formula (2) of [6] for the determinant of a tridiagonal matrix (\(\det A = a_{11}\det A[2,\ldots,n] - a_{21}a_{12}\det A[3,\ldots,n]\)), we have

$$\displaystyle\begin{array}{rcl} (A^{-1})_{ 11}& =& \frac{\det A[2,\ldots,n]} {\det A} = \frac{\det A[2,\ldots,n]} {a_{11}\det A[2,\ldots,n] - a_{12}a_{21}\det A[3,\ldots,n]} \\ & \geq & \frac{\det A[2,\ldots,n]} {a_{11}\det A[2,\ldots,n]} \geq 1. {}\end{array}$$
(15)

Thus, by (13)–(15) we can derive

$$\displaystyle{ \|A^{-1}\|_{ F}^{2} =\| B^{-1}\|_{ F}^{2} + \left ((A^{-1})_{ 11}\right )^{2} +\sum _{ i=2}^{n}\beta _{ i}^{2} +\sum _{ i=2}^{n}\gamma _{ i}^{2} \geq \| B^{-1}\|_{ F}^{2} + C, }$$
(16)

for any 0 ≤ C ≤ 1. Let us consider \(\hat{C}= \frac{8n^{2}-4} {n^{2}(n+1)^{2}}\), observe that then \(0 \leq \hat{C}\leq 1\) for all n > 2 and thus, by (14) and (16), we have

$$\displaystyle{\|A^{-1}\|_{ F}^{2} \geq \| B^{-1}\|_{ F}^{2} + \hat{C}\geq \left (\frac{2n - 2} {n} \right )^{2} + \frac{8n^{2} - 4} {n^{2}(n + 1)^{2}} = \left ( \frac{2n} {n + 1}\right )^{2}}$$

and the results holds.

4 Inequality for a General Class of Matrices

In this section, we shall prove that the inequality of the conjecture recalled in the previous section also holds for more general classes of matrices and, in particular, for nonsingular TP matrices in \(\mathcal{D}_{n}\).

Our classes of matrices will be closed under Schur complements and will be formed by P-matrices (all its principal minors are positive) satisfying, in addition, a classical inequality called the Fisher inequality:

$$\displaystyle{\det A \leq \det A[\alpha ]\det A(\alpha )}$$

for any α ∈ Q k, n and 1 ≤ k < n.

Theorem 4

Let \(A \in \mathcal{C}_{n} \cap \mathcal{D}_{n}\) , where \(\mathcal{C}_{n}\) is any class of n × n P-matrices closed under Schur complements and satisfying the Fisher inequality. Then

$$\displaystyle{\|A^{-1}\|_{ F} \geq \frac{2n} {n + 1}.}$$

Proof

We proceed by induction on n. If n = 2 it is known (see [16]) that \(\|A^{-1}\|_{F} \geq \sqrt{2}> 4/3\).

Suppose that the result holds for matrices of order n − 1; that is, given \(\tilde{A} \in \mathcal{C}_{n-1} \cap \mathcal{D}_{n-1}\), then \(\|\tilde{A}^{-1}\|_{F} \geq \frac{2n-2} {n}\). Consider now \(A \in \mathcal{C}_{n} \cap \mathcal{D}_{n}\). Since A is a P-matrix, we have that a 11 > 0. Then, after the first step in Gaussian elimination, we have A (2) = (a ij (2))1 ≤ i, j ≤ n (see Eq. (12))

$$\displaystyle{A^{(2)} = \left (\begin{array}{c|ccc} a_{11} & a_{12} & & \\ \hline 0& & & \\ \vdots & &A^{(2)}[2,\ldots,n]& \\ 0 & & & \end{array} \right )}$$

where a i1 (2) = 0 for all i ∈ { 2, …, n} and a 11 (2) = a 11 ≠ 0. Observe that we can express \(A = L_{1}^{-1}A^{(2)}\) ( = : (a ij )1 ≤ i, j ≤ n ), where

$$\displaystyle{L_{1} = \left (\begin{array}{*{10}c} 1 & & & \\ \frac{-a_{21}} {a_{11}} & 1& &\\ \vdots & &\ddots& \\ \frac{-a_{n1}} {a_{11}} & & & 1 \end{array} \right ).}$$

Thus, we have that (13) holds. Since A (2) is nonsingular we have that B: = A (2)[2, …, n] is also nonsingular. Taking into account that \(A \in \mathcal{D}_{n}\) is a P-matrix and considering Gaussian elimination, we have that either

$$\displaystyle{a_{ij}^{(2)} = a_{ ij} \in [0,1]}$$

or

$$\displaystyle{a_{ij}^{(2)} = a_{ ij} - \frac{a_{i1}} {a_{11}}a_{1j} \leq a_{ij} \leq 1}$$

and

$$\displaystyle{a_{ij}^{(2)} = a_{ ij} - \frac{a_{i1}} {a_{11}}a_{1j} = \frac{\det A[1,i\vert 1,j]} {a_{11}}> 0.}$$

Thus \(B \in \mathcal{D}_{n-1}\). Furthermore, observe that B can be expressed as the Schur complement \(B = A/A[1]\) and so \(B \in \mathcal{C}_{n-1}\). In conclusion, \(B \in \mathcal{C}_{n-1} \cap \mathcal{D}_{n-1}\). Thus, by the induction hypothesis, we have that (14) holds. Since \(A \in \mathcal{C}_{n}\), Fisher’s inequality implies that detA ≤ a 11detA[2, …, n] and, taking also into account that \(A \in \mathcal{D}_{n}\), we have

$$\displaystyle{ (A^{-1})_{ 11} = \frac{\det A[2,\ldots,n]} {\det A} \geq \frac{\det A[2,\ldots,n]} {a_{11}\det A[2,\ldots,n]} \geq 1. }$$
(17)

Thus, by (13), (14) and (17) we can derive (16) for any 0 ≤ C ≤ 1. Let us consider \(\hat{C}= \frac{8n^{2}-4} {n^{2}(n+1)^{2}}\), observe that then \(0 \leq \hat{C}\leq 1\) for all n > 2 and thus, by (14) and (16), we have

$$\displaystyle{\|A^{-1}\|_{ F}^{2} \geq \| B^{-1}\|_{ F}^{2} + \hat{C}\geq \left (\frac{2n - 2} {n} \right )^{2} + \frac{8n^{2} - 4} {n^{2}(n + 1)^{2}} = \left ( \frac{2n} {n + 1}\right )^{2}}$$

and the results holds.

As a consequence of the previous result, we can extend the result of the previous section to all nonsingular TP matrices.

Corollary 3

Let \(A \in \mathcal{D}_{n}\) be a nonsingular TP matrix. Then

$$\displaystyle{\|A^{-1}\|_{ F} \geq \frac{2n} {n + 1}.}$$

Proof

By Theorem 4, it is sufficient to see that the class of nonsingular TP matrices is a class of P-matrices closed under Schur complements and satisfying the Fisher inequality. By Ando [2, Corollary 3.8], nonsingular TP matrices are P-matrices. It is well known that they are closed under Schur complements (cf. [2, Theorem 3.3]). Finally, it is also well known that they satisfy the Fisher inequality (cf. [17]).

If we consider a nonsingular (tridiagonal) TP matrix A, observe that the lower bound provided in Sects. 3 and 4 for the norm of A −1 could imply an ill conditioning of A. However we have presented, in Sect. 2, accurate computations for these classes of matrices that do not depend on the conditioning of the initial matrix.