非奇异M-矩阵及其最小特征值理论常被应用于研究经济学中的投入-产出分析和增长模型、物理学中数字电路的偏微分方程动力系统以及概率统计中的Markov链等问题^[1-2].矩阵的Hadamard积则被广泛应用于正定矩阵特征值、奇异值的估计等研究^[3].最近，非奇异M-矩阵B与非奇异M-矩阵A的逆矩阵A^-1的Hadamard积的最小特征值τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)的下界估计成为许多学者关注和研究的热点问题，并得到了一系列估计式^[4-10].本文继续这一问题的研究，给出τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)单调递增收敛的下界序列.

1 预备知识

用R^n×n(C^n×n)表示n(n≥2) 阶实(复)矩阵集, I表示单位矩阵, 令N={1, 2, …, n}.

定义1^[1]   若A=[a_ij]∈R^n×n的任意元素a_ij≥0, 则称A为非负矩阵，记为A≥0.

定义2^[1]   若A≥0满足$\sum\limits_{i = 1}^n {{a_{ij}} = 1} $, j∈N, 则称A为随机矩阵.若A还满足$\sum\limits_{i = 1}^n {{a_{ij}} = 1} $, i∈N, 则称A为双随机矩阵.

定义3^[1]   设A=[a_ij], B=[b_ij]∈C^m×n, 用$\boldsymbol{A} \circ \boldsymbol{B}$表示A和B的对应元素相乘而得的m×n矩阵，即$\boldsymbol{A} \circ \boldsymbol{B}$=[a_ijb_ij], 称其为A和B的Hadamard积.

定义4^[2]   若A=[a_ij]∈R^n×n的非主对角线元非正，即a_ij≤0, i≠j, i, j∈N, 且A^-1≥0, 则称A为非奇异M-矩阵.用M_n表示非奇异M-矩阵的集合，称τ(A)=min{|λ|:λ∈σ(A)}为A的最小特征值，其中σ(A)为A的谱.

注1   由文献[2]知，若A为非奇异M-矩阵，则0 < τ(A)≤a_ii, i∈N; 若A, B均为非奇异M-矩阵，则$\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$也是一个非奇异M-矩阵.

为叙述方便先给出一些记号.设A=[a_ij]∈R^n×n, a_ii≠0.∀i, j, k∈N, j≠i, 记

$ {r_i} = \mathop {\max }\limits_{j \ne i} \left\{ {\frac{{\left| {{a_{ji}}} \right|}}{{\left| {{a_{ji}}} \right| - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|} }}} \right\},{m_{ji}} = \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{r_i}} }}{{\left| {{a_{ji}}} \right|}}, $

$ {m_i} = \mathop {\max }\limits_{j \ne i} \left\{ {{m_{ij}}} \right\},{u_{ji}} = \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{m_{ki}}} }}{{\left| {{a_{jj}}} \right|}}, $

$ {u_i} = \mathop {\max }\limits_{j \ne i} \left\{ {{u_{ij}}} \right\},{h_i} = \mathop {\max }\limits_{j \ne i} \left\{ {\frac{{\left| {{a_{ji}}} \right|}}{{\left| {{a_{jj}}} \right|{m_{ji}} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{m_{ki}}} }}} \right\}, $

$ {w_{ji}} = \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{m_{ki}}{h_i}} }}{{\left| {{a_{jj}}} \right|}},{w_i} = \mathop {\max }\limits_{j \ne i} \left\{ {{w_{ij}}} \right\}. $

2009年李耀堂等^[4]给出了如下结果：

设A=[a_ij]∈M_n, 且A^-1是双随机矩阵，则

$ \tau \left( {\mathit{\boldsymbol{A}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{a_{ii}} - {m_i}\sum\limits_{j \ne i} {\left| {{a_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {{m_{ji}}} }}} \right\}. $

(1)

2013年周端美等^[5]给出如下结果：

设A=[a_ij], B=[b_ij]∈M_n, 且A^-1是双随机矩阵，则

$ \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - {m_i}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {{m_{ji}}} }}} \right\}. $

(2)

同年，程光辉等^[6]给出如下结果：

设A=[a_ij]∈M_n, 且A^-1是双随机矩阵，则

$ \tau \left( {\mathit{\boldsymbol{A}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{a_{ii}} - {u_i}\sum\limits_{j \ne i} {\left| {{a_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {{u_{ji}}} }}} \right\}. $

(3)

不久，李耀堂等^[7]改进了式(1)~(3)，并给出以下结果：

设A=[a_ij], B=[b_ij]∈M_n, 且A^-1是双随机矩阵，则

$ \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - {w_i}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {{w_{ji}}} }}} \right\}; $

(4)

设A=[a_ij], B=[b_ij]∈M_n, 且A^-1=[α_ij], 则

$ \begin{array}{l} \tau \left( {\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}} \right) \ge \\ \mathop {\min }\limits_{i \ne j} \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4{\Delta _{ij}}} \right]}^{\frac{1}{2}}}} \right\}, \end{array} $

(5)

其中，Δ_ij=w_iw_jα_iiα_jj$\left( {\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)\left( {\sum\limits_{k \ne j} {\left| {{b_{kj}}} \right|} } \right)$.

下面分别给出τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)和τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)单调递增收敛的下界序列，新估计式改进了式(1)~(5)，且数值算例显示，τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)的下界序列可以达到真值.

2 主要结果

首先给出一些记号.设A=[a_ij]∈R^n×n, a_ii≠0. i, j, k∈N, j≠i, t=1, 2, …, 记

$ \begin{array}{l} w_{ji}^{\left( 0 \right)} = {w_{ji}},p_{ji}^{\left( t \right)} = \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|w_{ki}^{\left( {t - 1} \right)}} }}{{\left| {{a_{jj}}} \right|}},p_i^{\left( t \right)} = \\ \mathop {\max }\limits_{j \ne i} \left\{ {p_{ij}^{\left( t \right)}} \right\},h_i^{\left( t \right)} = \mathop {\max }\limits_{j \ne i} \left\{ {\frac{{\left| {{a_{ji}}} \right|}}{{\left| {{a_{jj}}} \right|p_{ji}^{\left( t \right)} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|p_{ki}^{\left( {t} \right)}} }}} \right\},\\ w_{ji}^{\left( t \right)} = \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|p_{ki}^{\left( {t} \right)}h_i^{\left( t \right)}} }}{{\left| {{a_{jj}}} \right|}}. \end{array} $

引理1   设A=[a_ij]∈R^n×n是行严格对角占优矩阵，则∀i, j∈N, j≠i, t=1, 2, …, 有

(ⅰ) 1>r_i≥m_ji≥u_ji≥w_ji=w_ji⁽⁰⁾≥p_ji⁽¹⁾≥w_ji⁽¹⁾≥ p_ji⁽²⁾≥w_ji⁽²⁾≥…≥p_ji^(t)≥w_ji^(t)≥…≥0;

(ⅱ)1≥h_i≥0, 1≥h_i^(t)≥0.

证明   因为A是行严格对角占优矩阵, 即$|{a_{jj}}| > \sum\limits_{k \ne j, i} {\left| {{a_{jk}}} \right| + \left| {{a_{ji}}} \right|} $, 则$0 \le \frac{{\left| {{a_{ji}}} \right|}}{{|{a_{jj}}|-\sum\limits_{k \ne j, i} {\left| {{a_{jk}}} \right|} }} < 1$.由r_i的定义知0≤r_i < 1.又${r_i} \ge \frac{{\left| {{a_{ji}}} \right|}}{{|{a_{jj}}|-\sum\limits_{k \ne j, i} {\left| {{a_{jk}}} \right|} }}$, 即${r_i} \ge \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j, i} {\left| {{a_{jk}}} \right|} {r_i}}}{{|{a_{jj}}|}} = {m_{ji}}$.由m_ji, u_ji的定义知1>r_i≥m_ji≥u_ji≥0.

因为

$ \begin{array}{l} \frac{{\left| {{a_{ji}}} \right|}}{{\left| {{a_{jj}}} \right|{m_{ji}} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{m_{ki}}} }} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\frac{{\left| {{a_{jj}}} \right|{m_{ji}} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{r_i}} }}{{\left| {{a_{jj}}} \right|{m_{ji}} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{m_{ki}}} }} \le 1, \end{array} $

由h_i的定义知0≤h_i≤1, 且

$ {h_i} \ge \frac{{\left| {{a_{ji}}} \right|}}{{\left| {{a_{jj}}} \right|{m_{ji}} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{m_{ki}}} }}, $

即

$ {m_{ji}}{h_i} \ge \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|{m_{ki}}{h_i}} }}{{\left| {{a_{jj}}} \right|}} = w_{ji}^{\left( 0 \right)}. $

由0≤h_i≤1知m_ji≥m_jih_i≥w_ji⁽⁰⁾≥0.再由u_ji, w_ji⁽⁰⁾, p_ji⁽¹⁾的定义知u_ji≥w_ji⁽⁰⁾≥p_ji⁽¹⁾≥0.

因为

$ \begin{array}{l} \frac{{\left| {{a_{ji}}} \right|}}{{\left| {{a_{jj}}} \right|p_{ji}^{\left( 1 \right)} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|p_{ki}^{\left( 1 \right)}} }} = \\ \;\;\;\;\;\;\;\;\;\frac{{\left| {{a_{jj}}} \right|p_{ji}^{\left( 1 \right)} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|w_{ki}^{\left( 0 \right)}} }}{{\left| {{a_{jj}}} \right|p_{ji}^{\left( 1 \right)} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|p_{ki}^{\left( 1 \right)}} }} \le 1, \end{array} $

由h_i⁽¹⁾的定义知0≤h_i⁽¹⁾≤1, i∈N, 且

$ h_i^{\left( 1 \right)} \ge \frac{{\left| {{a_{ji}}} \right|}}{{\left| {{a_{jj}}} \right|p_{ji}^{\left( 1 \right)} - \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|p_{ki}^{\left( 1 \right)}} }}, $

即

$ p_{ji}^{\left( 1 \right)}h_i^{\left( 1 \right)} \ge \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|p_{ki}^{\left( 1 \right)}h_i^{\left( 1 \right)}} }}{{\left| {{a_{jj}}} \right|}} = w_{ji}^{\left( 1 \right)}, $

由0≤h_i⁽¹⁾≤1知p_ji⁽¹⁾≥w_ji⁽¹⁾≥0.再由w_ji⁽¹⁾≥0, p_ji⁽²⁾的定义, 可得w_ji⁽¹⁾≥0≥p_ji⁽²⁾≥0.

用上述类似的方法, 可证

$ \begin{array}{*{20}{c}} {p_{ji}^{\left( 2 \right)} \ge w_{ji}^{\left( 2 \right)} \ge \cdots \ge p_{ji}^{\left( t \right)} \ge w_{ji}^{\left( t \right)} \ge \cdots \ge 0,}\\ {1 \ge h_i^{\left( t \right)} \ge 0,\;\;\;\;t = 2,3, \cdots .} \end{array} $

证毕.

应用引理1及类似于文献[4]中引理2.2和定理3.1的证明，可得

引理2   设A=[a_ij]∈R^n×n是行严格对角占优M-矩阵，则A^-1=[α_ij]存在, 且对任意j, i∈N, j≠i, t=0, 1, 2, …,

$ {\alpha _{ji}} \le \frac{{\left| {{a_{ji}}} \right| + \sum\limits_{k \ne j,i} {\left| {{a_{jk}}} \right|w_{ki}^{\left( t \right)}} }}{{\left| {{a_{jj}}} \right|}}{\alpha _{ii}} = p_{ji}^{\left( {t + 1} \right)}{\alpha _{ii}}. $

引理3设A=[a_ij]∈M_n, 且A^-1=[α_ij]是双随机矩阵，则${a_{ii}} \ge \frac{1}{{1 + \sum\limits_{j \ne i} {p_{ji}^{\left( t \right)}} }}$, i∈N, t=1, 2, ….

定理1设A=[a_ij], B=[b_ij]∈M_n, 且A^-1=[α_ij], 则对任意t=1, 2, …,

$ \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge {\Omega _t}, $

(6)

其中,

$ \begin{array}{*{20}{c}} {{\Omega _t} = \mathop {\min }\limits_{i \ne j} \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4\Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\},}\\ {\Upsilon _{ij}^{\left( t \right)} = p_i^{\left( t \right)}p_j^{\left( t \right)}{\alpha _{ii}}{\alpha _{jj}}\left( {\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)\left( {\sum\limits_{k \ne j} {\left| {{b_{kj}}} \right|} } \right).} \end{array} $

证明   由A∈M_n知，存在一个正对角矩阵D，使得D^-1AD是一个行严格对角占优M-矩阵^[2].由文献[2]引理5.1.2可得

$ \begin{array}{l} \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) = \tau \left( {{\mathit{\boldsymbol{D}}^{ - 1}}\left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right)\mathit{\boldsymbol{D}}} \right) = \tau \left( {\mathit{\boldsymbol{B}} \circ \left( {{\mathit{\boldsymbol{D}}^{ - 1}}{\mathit{\boldsymbol{A}}^{ - 1}}\mathit{\boldsymbol{D}}} \right)} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\tau \left( {\mathit{\boldsymbol{B}} \circ {{\left( {{\mathit{\boldsymbol{D}}^{ - 1}}\mathit{\boldsymbol{AD}}} \right)}^{ - 1}}} \right). \end{array} $

为方便起见，且不失一般性，可设A是行严格对角占优M-矩阵.

(ⅰ)设A和B均为不可约矩阵, 则对任意i∈N, 有0 < p_i^(t) < 1.令τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)=λ, 由注1得0 < λ≤b_iiα_ii, i∈N.由文献[10]引理2.5知，存在一组i, j, i≠j, 使得

$ \begin{array}{l} \left| {\lambda - {b_{ii}}{\alpha _{ii}}} \right|\left| {\lambda - {b_{jj}}{\alpha _{jj}}} \right| \le \\ \left( {p_i^{\left( t \right)}\sum\limits_{k \ne i} {\frac{1}{{p_k^{\left( t \right)}}}\left| {{b_{ki}}{\alpha _{ki}}} \right|} } \right)\left( {p_j^{\left( t \right)}\sum\limits_{k \ne j} {\frac{1}{{p_k^{\left( t \right)}}}\left| {{b_{kj}}{\alpha _{kj}}} \right|} } \right) \le \\ \left( {p_i^{\left( t \right)}\sum\limits_{k \ne i} {\frac{1}{{p_k^{\left( t \right)}}}\left| {{b_{ki}}p_{ki}^{\left( t \right)}{\alpha _{ii}}} \right|} } \right)\left( {p_j^{\left( t \right)}\sum\limits_{k \ne j} {\frac{1}{{p_k^{\left( t \right)}}}\left| {{b_{kj}}p_{kj}^{\left( t \right)}{\alpha _{jj}}} \right|} } \right) \le \\ \left( {p_i^{\left( t \right)}\sum\limits_{k \ne i} {\frac{1}{{p_k^{\left( t \right)}}}\left| {{b_{ki}}p_k^{\left( t \right)}{\alpha _{ii}}} \right|} } \right)\left( {p_j^{\left( t \right)}\sum\limits_{k \ne j} {\frac{1}{{p_k^{\left( t \right)}}}\left| {{b_{kj}}p_k^{\left( t \right)}{\alpha _{jj}}} \right|} } \right) = \\ \left( {p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)\left( {p_j^{\left( t \right)}{\alpha _{jj}}\sum\limits_{k \ne j} {\left| {{b_{kj}}} \right|} } \right) = \Upsilon _{ij}^{\left( t \right)}, \end{array} $

即

$ \left( {\lambda - {b_{ii}}{\alpha _{ii}}} \right)\left( {\lambda - {b_{jj}}{\alpha _{jj}}} \right) \le \Upsilon _{ij}^{\left( t \right)}, $

(7)

由式(7) 得

$ \lambda \ge \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4\Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\}, $

由此得

$ \begin{array}{l} \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge \\ \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4\Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\} \ge \\ \mathop {\min }\limits_{i \ne j} \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4\Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\}. \end{array} $

(ⅱ)假设A和B中至少有1个是可约矩阵.由文献[2]知, Z_n={A=[a_ij]∈R^n×n|a_ij≤0, i≠j, i, j∈N}中的矩阵是非奇异M-矩阵的充分必要条件是其所有顺序主子式为正.定义V=[v_ij]是n阶置换阵，其中v₁₂=v₂₃=…=v_{n-1, n}=v_n1=1, 其余v_ij为0.对任意正数ε>0, 当ε充分小时，可知A-εV和B-εV的所有顺序主子式都为正，所以A-εV和B-εV都是不可约非奇异M-矩阵.然后用A-εV和B-εV分别代替A和B，并令ε→0，利用连续性可得式(6) 成立.证毕.

定理2   由定理1得到的下界序列{Ω_t}, t=1, 2, …是单调递增的且以τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)为上界, 因而该序列是收敛的.

证明   由引理1知，对任意i, j∈N, i≠j, t=1, 2, …, 有p_ji^(t)≥p_ji^(t+1)≥0, 所以序列{p_ji^(t)}和{p_i^(t)}均单调递减.由此序列{Ω_t}, t=1, 2, …单调递增且有上界τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$), 故该序列是收敛的.证毕.

在定理1中取B=A，可得

推论1   设A=[a_ij]∈M_n, 且A^-1=[α_ij]，则对任意t=1, 2, …，

$ \tau \left( {\mathit{\boldsymbol{A}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge {{\bar \Omega }_t}, $

(8)

其中，

$ \begin{array}{*{20}{c}} {{{\bar \Omega }_t} = \mathop {\min }\limits_{i \ne j} \frac{1}{2}\left\{ {{a_{ii}}{\alpha _{ii}} + {a_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{a_{ii}}{\alpha _{ii}} - {a_{jj}}{\alpha _{jj}}} \right)}^2} + 4\bar \Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\},}\\ {\bar \Upsilon _{ij}^{\left( t \right)} = p_i^{\left( t \right)}p_j^{\left( t \right)}{\alpha _{ii}}{\alpha _{jj}}\left( {\sum\limits_{k \ne i} {\left| {{a_{ki}}} \right|} } \right)\left( {\sum\limits_{k \ne j} {\left| {{a_{kj}}} \right|} } \right).} \end{array} $

定理3   设A=[a_ij], B=[b_ij]∈M_n, 且A^-1=[α_ij], 则对任意t=1, 2, …, 有

$ \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge {\Omega _t} \ge \mathop {\min }\limits_{i \ne {\bf{N}}} \left\{ {\frac{{{b_{ii}} - p_i^{\left( t \right)}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{{a_{ii}}}}} \right\}. $

证明   由A=[a_ij]∈M_n知A^-1=[α_ij]≥0.因为AA^-1=I, 所以

$ 1 = \sum\limits_{j = 1}^n {{a_{ij}}{\alpha _{ij}}} = {a_{ii}}{\alpha _{ii}} - \sum\limits_{j \ne i} {\left| {{a_{ij}}} \right|{\alpha _{ji}}} ,i \in {\bf{N}}, $

从而a_iiα_ii≥1, i∈N, 即α_ii≥$\frac{1}{{{a_{ii}}}}$, i∈N.

对任意i, j∈N, i≠j, 不失一般性，假设

$ {b_{ii}}{\alpha _{ii}} - p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} \le {b_{jj}}{\alpha _{jj}} - p_j^{\left( t \right)}{\alpha _{jj}}\sum\limits_{k \ne j} {\left| {{b_{kj}}} \right|} , $

即

$ p_j^{\left( t \right)}{\alpha _{jj}}\sum\limits_{k \ne j} {\left| {{b_{kj}}} \right|} \le {b_{jj}}{\alpha _{jj}} - {b_{ii}}{\alpha _{ii}} + p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} . $

从而

$ \begin{array}{l} \Upsilon _{ij}^{\left( t \right)} = \left( {p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)\left( {p_j^{\left( t \right)}{\alpha _{jj}}\sum\limits_{k \ne j} {\left| {{b_{kj}}} \right|} } \right) \le \\ \left( {p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)\left( {{b_{jj}}{\alpha _{jj}} - {b_{ii}}{\alpha _{ii}} + p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right). \end{array} $

进一步

$ \begin{array}{l} \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4\bar \Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\} \ge \\ \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - \left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4\left( {p_i^{\left( t \right)}{\alpha _{ii}} \times } \right.} \right.} \right.\\ \left. {{{\left. {\left. {\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)\left( {{b_{jj}}{\alpha _{jj}} - {b_{ii}}{\alpha _{ii}} + p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)} \right]}^{\frac{1}{2}}}} \right\} = \\ \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - \left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4\left( {p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right) \times } \right.} \right.\\ \left. {{{\left. {\left( {{b_{jj}}{\alpha _{jj}} - {b_{ii}}{\alpha _{ii}}} \right) + 4{{\left( {p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)}^2}} \right]}^{\frac{1}{2}}}} \right\} = \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + } \right.\\ \left. {{b_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{b_{jj}}{\alpha _{jj}} - {b_{ii}}{\alpha _{ii}} + 2p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)}^2}} \right]}^{\frac{1}{2}}}} \right\} = \\ \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - \left( {{b_{jj}}{\alpha _{jj}} - {b_{ii}}{\alpha _{ii}} + 2p_i^{\left( t \right)}{\alpha _{ii}}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right)} \right\} = \\ \left( {{b_{ii}} - p_i^{\left( t \right)}\sum\limits_{k \ne i} {\left| {{b_{ki}}} \right|} } \right){\alpha _{ii}} \ge \frac{{{b_{ii}} - p_i^{\left( t \right)}\sum\limits_{k \ne i} {\left| {{b_{ji}}} \right|} }}{{{a_{ii}}}} \ge \\ \mathop {\min }\limits_{i \ne {\bf{N}}} \left\{ {\frac{{{b_{ii}} - p_i^{\left( t \right)}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{{a_{ii}}}}} \right\}. \end{array} $

从而

$ \begin{array}{*{20}{c}} {{\Omega _t} = \mathop {\min }\limits_{i \ne j} \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - \left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + } \right.} \right.}\\ {\left. {{{\left. {4\Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\} \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{{\rm{b}}_{{\rm{ii}}}} - {\rm{p}}_{\rm{i}}^{\left( {\rm{t}} \right)}\sum\limits_{{\rm{j}} \ne {\rm{i}}} {\left| {{{\rm{b}}_{{\rm{ji}}}}} \right|} }}{{{{\rm{a}}_{{\rm{ii}}}}}}} \right\}.} \end{array} $

证毕.

由定理3易得

推论2   设A=[a_ij], B=[b_ij]∈M_n, 则对任意t=1, 2, …, 有

$ \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - p_i^{\left( t \right)}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{{a_{ii}}}}} \right\}. $

(9)

在定理3和推论2中分别取B=A，可得

推论3   设A=[a_ij]∈M_n, 且A^-1=[α_ij], 则对任意t=1, 2, …, 有

$ \tau \left( {\mathit{\boldsymbol{A}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge {{\bar \Omega }_t} \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {1 - \frac{{p_i^{\left( t \right)}}}{{{a_{ii}}}}\sum\limits_{j \ne i} {\left| {{a_{ji}}} \right|} } \right\}. $

由引理3及类似于定理3、推论2和推论3的证明，可得

定理4   设A=[a_ij], B=[b_ij]∈M_n, 且A^-1=[α_ij]是双随机矩阵，则对任意t=1, 2, …, 有

$ \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge {\Omega _t} \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - p_i^{\left( t \right)}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {p_{ji}^{\left( t \right)}} }}} \right\}. $

推论4   设A=[a_ij], B=[b_ij]∈M_n, 且A^-1是双随机矩阵，则对任意t=1, 2, …, 有

$ \tau \left( {\mathit{\boldsymbol{B}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - p_i^{\left( t \right)}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {p_{ji}^{\left( t \right)}} }}} \right\}. $

(10)

推论5   设A=[a_ij]∈M_n, 且A^-1=[α_ij]是双随机矩阵，则对任意t=1, 2, …, 有

$ \tau \left( {\mathit{\boldsymbol{A}} \circ {\mathit{\boldsymbol{A}}^{ - 1}}} \right) \ge {{\bar \Omega }_t} \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{a_{ii}} - p_i^{\left( t \right)}\sum\limits_{j \ne i} {\left| {{a_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {p_{ji}^{\left( t \right)}} }}} \right\}. $

注2   首先对式(2)~(6)(9)(10) 做一简单比较：

(ⅰ)设A=[a_ij], B=[b_ij]∈M_n.由于式(9) 仅用A, B的元素即可对τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)进行估计, 而式(2)(4) 和(10) 要求A^-1=[α_ij]是双随机矩阵; 式(5) 和(6) 要求A^-1=[α_ij]的所有主对角线元素已知, 此时仅有式(9) 可给出τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)的估计.由于式(9) 的前提条件弱于式(2)(4)~(6) 和(10)，因此其适用范围更广.

(ⅱ)设A=[a_ij], B=[b_ij]∈M_n且A^-1是双随机矩阵.由引理1知，对任意j, i∈N, j≠i, t=1, 2, …, 有1>m_ji≥u_ji≥w_ji≥p_ji^(t)≥0.再由m_i, u_i, w_i, p_i^(t)的定义知，1>m_i≥u_i≥w_i≥p_i^(t)≥0, i∈N.显然

$ \begin{array}{*{20}{c}} {\mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - p_i^{\left( t \right)}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {p_{ji}^{\left( t \right)}} }}} \right\} \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - {w_i}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {{w_{ji}}} }}} \right\} \ge }\\ {\mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - {u_i}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {{u_{ji}}} }}} \right\} \ge \mathop {\min }\limits_{i \in {\bf{N}}} \left\{ {\frac{{{b_{ii}} - {m_i}\sum\limits_{j \ne i} {\left| {{b_{ji}}} \right|} }}{{1 + \sum\limits_{j \ne i} {{m_{ji}}} }}} \right\}.} \end{array} $

由此知，此时式(10) 的估计优于式(2) 和(4).

(ⅲ)设A=[a_ij], B=[b_ij]∈M_n且A^-1=[α_ij]的主对角线元素α_ii(i∈N)已知.由(ⅱ)知，对任意j, i∈N, j≠i, t=1, 2, …, 有1>w_i≥p_i^(t)≥0, 显然式(6) 的估计优于式(5).

由定理3知，式(6) 的估计优于式(9).

由于式(6) 无须A^-1是双随机矩阵，故由式(6) 可以给出τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)的估计，而此时式(2)(4) 和(10) 均不适用.

(ⅳ)设A=[a_ij], B=[b_ij]∈M_n, A^-1=[α_ij]是双随机矩阵, 且其主对角线元素α_ii, i∈N已知.由定理4知式(6) 的估计优于式(10)；由(ⅱ)知，式(10) 的估计优于式(2) 和(4)；由(ⅲ)知，式(6) 的估计优于式(5) 和(9)；从而式(6) 的估计优于式(2)(4)(5)(9) 和(10).

(ⅴ)从算法的时间复杂性来看，式(2)(4)~(6)(9) 和(10) 的时间复杂性是一样的，均为O(n³).

与定理1、定理2和推论1的证明类似，可得

定理5   设A=[a_ij], B=[b_ij]∈M_n, 且A^-1=[α_ij], 则对任意t=1, 2, …, τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)≥${{\hat \Omega }_t}$,

其中，

$ \begin{array}{l} {{\hat \Omega }_t} = \mathop {\min }\limits_{i \ne j} \frac{1}{2}\left\{ {{b_{ii}}{\alpha _{ii}} + {b_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{b_{ii}}{\alpha _{ii}} - {b_{jj}}{\alpha _{jj}}} \right)}^2} + 4\hat \Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\},\\ \hat \Upsilon _{ij}^{\left( t \right)} = {m_i}{m_j}{\alpha _{ii}}{\alpha _{jj}}\left( {\sum\limits_{k \ne i} {\frac{{\left| {{b_{ki}}} \right|p_{ki}^{\left( t \right)}}}{{{m_k}}}} } \right)\left( {\sum\limits_{k \ne j} {\frac{{\left| {{b_{kj}}} \right|p_{kj}^{\left( t \right)}}}{{{m_k}}}} } \right). \end{array} $

定理6   由定理5得到的下界序列{${{\hat \Omega }_t}$}, t=1, 2, …是单调递增的且以τ($\boldsymbol{B} \circ {\boldsymbol{A}^{ - 1}}$)为上界, 因而该序列是收敛的.

推论6   设A=[a_ij]∈M_n, 且A^-1=[α_ij], 则对任意t=1, 2, …, τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)≥${\widetilde \Omega _t}$, 其中，

$ \begin{array}{l} {{\tilde \Omega }_t} = \mathop {\min }\limits_{i \ne j} \frac{1}{2}\left\{ {{a_{ii}}{\alpha _{ii}} + {a_{jj}}{\alpha _{jj}} - {{\left[ {{{\left( {{a_{ii}}{\alpha _{ii}} - {a_{jj}}{\alpha _{jj}}} \right)}^2} + 4\hat \Upsilon _{ij}^{\left( t \right)}} \right]}^{\frac{1}{2}}}} \right\},\\ \hat \Upsilon _{ij}^{\left( t \right)} = {m_i}{m_j}{\alpha _{ii}}{\alpha _{jj}}\left( {\sum\limits_{k \ne i} {\frac{{\left| {{a_{ki}}} \right|p_{ki}^{\left( t \right)}}}{{{m_k}}}} } \right)\left( {\sum\limits_{k \ne j} {\frac{{\left| {{a_{kj}}} \right|p_{kj}^{\left( t \right)}}}{{{m_k}}}} } \right). \end{array} $

令${L_t} = \max \left\{ {{{\bar \Omega }_t}, {{\widetilde \Omega }_t}} \right\}$, 则由推论1和推论6易得

定理7   设A=[a_ij]∈M_n, 且A^-1=[α_ij], 则对任意t=1, 2, …, τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)≥L_t.

3 数值算例

例1   设

$ \mathit{\boldsymbol{A}} = \left[ {\begin{array}{*{20}{c}} {21}&{ - 1}&{ - 2}&{ - 3}&{ - 4}&{ - 1}&{ - 1}&{ - 3}&{ - 2}&{ - 3}\\ { - 1}&{18}&{ - 3}&{ - 1}&{ - 1}&{ - 4}&{ - 2}&{ - 1}&{ - 3}&{ - 1}\\ { - 2}&{ - 1}&{10}&{ - 1}&{ - 1}&{ - 1}&0&{ - 1}&{ - 1}&{ - 1}\\ { - 3}&{ - 1}&0&{16}&{ - 4}&{ - 2}&{ - 1}&{ - 1}&{ - 1}&{ - 2}\\ { - 1}&{ - 3}&0&{ - 2}&{15}&{ - 1}&{ - 1}&{ - 1}&{ - 1}&{ - 2}\\ { - 3}&{ - 2}&{ - 1}&{ - 1}&{ - 1}&{12}&{ - 2}&0&{ - 1}&0\\ { - 1}&{ - 3}&{ - 1}&{ - 1}&0&{ - 1}&9&0&{ - 1}&0\\ { - 3}&{ - 1}&{ - 1}&{ - 4}&{ - 1}&0&0&{12}&0&{ - 1}\\ { - 2}&{ - 4}&{ - 1}&{ - 1}&{ - 1}&0&{ - 1}&{ - 3}&{14}&0\\ { - 4}&{ - 1}&0&{ - 1}&{ - 1}&{ - 1}&0&{ - 1}&{ - 2}&{12} \end{array}} \right]. $

由Matlab(R2009a)计算得A^-1≥0, 再由定义2和定义4知A∈M₁₀且A^-1是双随机矩阵.取迭代总次数为10, 由式(1)(3)、定理7和文献[7-10]中相关结论得到的数值结果及所需时间如表 1所示，其中t表示迭代次数.事实上, τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)=0.968 7.

从表 1可看出，由定理7得到的τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)的下界序列是单调递增的，且大于由式(1)(3) 和文献[7-10]中相关结果得到的下界.从达到下界所需时间看, 定理7所需时间比式(1)(3) 和文献[7, 9-10]中相关结果略长，比文献[8]定理11短.

例2   设矩阵A=[a_ij]∈R^n×n是由Matlab(R2009a)随机产生的逆为双随机矩阵的非奇异M-矩阵(满足0-1分布).取迭代总次数为500，由定理7得到的数值结果的部分数据列于表 2, 其中t为迭代次数.

表 2的数值结果显示，当矩阵的阶很大时，由定理7估计τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)是非常有效的.

例3   设A=[a_ij]∈R^100×100, 其中, a₁₁=a₂₂=…=a_{100, 100}=2, a₁₂=a₂₃=…=a_{99, 100}=a_{100, 101}=-1, 其余a_ij=0.易知A∈M₁₀₀, 且A^-1=[α_ij]是双随机矩阵.取迭代总次数为10，当t=1时，由定理7得τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)≥0.750 0.事实上，τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)=$\frac{3}{4}$.例3表明，由定理7得到的τ($\boldsymbol{A} \circ {\boldsymbol{A}^{ - 1}}$)的下界序列可以达到真值.