关于Kahan定理的一个注记

设A∈C~(n×n),B∈C~(k×k)均为Hermite矩阵,它们的特征值分别为{λ_j}_(j=1)~n和{μ_j}_(j=1)~k(k≤n);Q∈~(n×k)为列满秩矩阵.令 (1) 则存在A的k个特征值λ_(j_2),λ_(j_2),…,λ_(j_k),使得 (2) 其中σ_k为Q的最小奇异值,||·||_2表示矩阵的谱范数.这是著名的Kahan定理·1996年曹志浩等在[2]中将(2)加强为 (3) 这是Kahan的猜想.在本文中,我们讨论将Kahan定理中“B为k阶Hermite矩阵”改为B为k阶(任意)方阵后,特征值的扰动估计,有以下结果. 定理 设A∈C~(n×n)为Hermite矩阵,其特征值为{λ_j}_(j=1)~n,B∈C~(k×k)的特征值为{μ_j}_(j=1)~k,而Q∈C~(n×k)为列满秩矩阵.则存在A的k个特征值λ_(j_1),λ_(j_2),…,λ_(j_k),使得     

上期问题解答

<正> 1.证明:当r=0时,结论显然成立。假定r>0,记λ_1≥λ_2≥…≥λ_n为A的特征根,则A~2的特征根为λ_2~2≥…≥λ_n~2。因A的秩为r,故λ_1≥…≥λ_r>0,λ_(r+1)=…=λ_1=0。考虑S=sub from i=1 to r(λ_i一λ)~1,     

解广义特征值反问题的同伦方法

1.引言 我们讨论下列广义特征值反问题: (G)已知B是n×n阶对称半正定矩阵,λ=(λ_1,…,λ_(2n-1))~T∈R~(2n-1),且{λ_i}~(n_3),和{λ_i}_(n+1)~(2n-1)严格交错。问题是欲求一个实对称三对角n×n阶矩阵A,使得λ_1…,λ_n是Ax=λBx的特征值,λ_(n+1),…,λ_(2n-1)是A_(n-1)x=λB_(n-1)x的特征值,其中A_(n-1),B_(n-1)分别是矩阵A,B的前n-1阶主子阵。     

矩阵特征值的几个扰动定理

1 引言 设A∈C~(n×m),B∈C~(m×m)(m≤n),它们的特征值分别为{λ_k}_(k=1)~n和{μ_k}_(k=1)~m.令 R=AQ-QB (1)这里Q∈C~(n×m)为列满秩矩阵.Kahan研究了矩阵A在C~(n×m)上的Rayleigh商的性质,证明了下列定理:设A为Hermite矩阵,Q为列正交矩阵,即Q~HQ=I,而B=Q~HAQ,则存在 1,2,… ,n的某个排列π,使得 {sum from j=1 to m │μ_j-λ_(π(j))│~2}~(1/2)≤2~(1/2)‖R‖_F (2)其中R如(1)所示,‖·‖_F为矩阵的Frobenius范数.刘新国在[2]中将此定理推广到B为可对角化矩阵的情形,并且还建立了较为一般的扰动定理:设A为正规矩阵,B为可对角化矩阵;存在非奇异矩阵G,使得G~(-1)BG为对角阵,则存在1,2,…,n的某个排列π,使得 │μ_j-λ_(π(j))│≤2(2~(1/2))nK(G)_(σ_m~(-1))‖R‖_F,j=1,2,…,m. (3)     

SPN—矩阵谱的一个特性条件

设A=(a_(ij))是n×n实矩阵,A的谱{λ_1,λ_2,…,λ_n}满足ρ(A)=|λ_1|≥|λ_2|≥…≥|λ_n|。如果A的每个奇数阶主子式是(非负)正的且每个偶数阶主子式是(非正)负的,则称A是(半)PN—矩阵。在过去的十几年里,PN—矩阵类和半PN—矩阵类在经济学文献中已引起足够的重视[1],因为每个主子式皆为负(非正)的矩阵被     

关于完备λ超曲面的第二拼挤定理

欧氏空间R~(n+1)中满足方程H=-X~N+λ的浸入超曲面称为λ超曲面.本文主要研究欧氏空间中完备λ超曲面的第二拼挤问题.设M为R~(n+1)中具有多项式体积增长的n维完备λ超曲面.设M的第二基本形式为A.本文证明存在正的绝对常数γ,如果|λ|≤γ,β_λ≤|A|~2≤β_λ+~1/21,其中β_λ=1/2(2+λ~2+|λ|(λ~2+4)~1/2),那么|A|~2≡β_λ,λ≥0,且M必为n维球面S~n(n~1/2)、n维圆柱面S~k(k~1/2)×R~(n-k)(1≤ k≤ n-1)或S(((λ2+4)~1/2-|λ|)/2)×R~(n-1)之一.     

关于两个正定矩阵之积的特征值估计的一个注记

令A>0及B>0记两个n×n(n≥2)厄尔米特正定矩阵;μ_1≥μ_2≥…μ_n及ν_1≥ν_2≥…≥ν_n记A和B的特征值;设λ为AB的任意特征值.ShaHu-yun证得2/nμ_n~2ν_n~2/μ_n~2 ν_n~2<λ相似文献   

输出反馈极点配置问题的一个算法

在线性多变量控制理论中,存在一个代数特征值反问题——输出反馈极点配置问题。问题叙述如下: 问题PAO.给定A∈R~(n×n),B∈R_m~(n×m),C∈R_p~(p×n)和?={λ_1,λ_2,…,λ_n},?在复共轭下封闭.求K∈R~(m×p),使得A+BKC具有事先给定的特征值λ_1,λ_2,…,λ_n。 [2]和[5]等证明了     

与三角形边上定比分点有关的几个比值

命题1 设点A_1、B_1、C_1分别位于△ABC的三边BC、CA、AB上(或其延长线上)(图1),若BA_1/BV=λ_1,CB_1/CA=λ_2,AC_1/AB=λ_3。则S_1/S=1-(λ_1 λ_2 λ_3) (λ_1λ_2 λ_2λ_3 λ_3λ_1)。(1)     

矩阵特征值与特征向量的一个反问题

1995年全国工学硕士研究生入学考试(试卷一)有一道试题:设三阶实对称矩阵A的特征值为λ_1=-1,λ_2=λ_3=1,对应于λ_1的特征向量为 ε_1=(0,1,1)~T,求A.对此题,许多考生为以下两个问题而困惑:     

Extensions to a Lagrangean relaxation approach for the capacitated warehouse location problem

In this paper we present a lower bound for the capacitated warehouse location problem based upon the Lagrangean relaxation of a mixed-integer formulation of the problem, where we use subgradient optimisation in an attempt to maximise this lower bound. Problem reduction tests based upon this lower bound and the original problem are given. Incorporating this bound and the reduction tests into a tree search procedure enables us to solve problems involving up to 50 warehouses and 150 customers.     

Gap,cosum and product properties of the θ′ bound on the clique number

In a paper published in 1978, McEliece, Rodemich and Rumsey improved the Lovász bound θ for the maximum clique problem. This strengthening has become well known under the name Lovász–Schrijver bound and is usually denoted by θ′. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound and the actual clique number can be arbitrarily large, we establish homomorphy results for this bound under cosums and products of graphs. In particular we show that for circulant graphs of prime order there must be a positive gap between the clique number and the bound.     

A quadratic programming approach to the determination of an upper bound on the weighted stability number

In a previous work, the authors have introduced an upper bound on the stability number of a graph and several of its properties were given. The determination of this upper bound was done by a quadratic programming approach whose implementation has given good computational results. We now extend this bound to the weighted case, i.e., an upper bound on the weighted stability of an arbitrary graph with node weights is presented. Similarly to the non-weighted case, the deduced bound allows us to give a necessary and sufficient condition to a weighted graph that attains the given bound. Also a heuristic for determining the maximum weight stable set is proposed which is based on an integrality property of a convex quadratic problem that produces the bound. Some comments about the proposed approach will conclude the paper.     

Estimation of optimal backward perturbation bounds for the linear least squares problem

In this paper a method of estimating the optimal backward perturbation bound for the linear least squares problem is presented. In contrast with the optimal bound, which requires a singular value decomposition, this method is better suited for practical use on large problems since it requiresO(mn) operations. The method presented involves the computation of a strict lower bound for the spectral norm and a strict upper bound for the Frobenius norm which gives a gap in which the optimal bounds for the spectral and the Frobenius norm must be. Numerical tests are performed showing that this method produces an efficient estimate of the optimal backward perturbation bound.     

A Lagrangian lower bound for the container transshipment problem at a railway hub for a fast branch-and-bound algorithm

In this paper, we consider the container transshipment problem at a railway hub. A simple lower bound known for this problem will be improved by a new Lagrangian relaxation lower bound. Computational tests show that this lower bound outperforms the simple one and decreases substantially the run time of the branch-and-bound algorithm.     

Lower bound theorem for normal pseudomanifolds

In this paper we present a self-contained combinatorial proof of the lower bound theorem for normal pseudomanifolds, including a treatment of the cases of equality in this theorem. We also discuss McMullen and Walkup's generalized lower bound conjecture for triangulated spheres in the context of the lower bound theorem. Finally, we pose a new lower bound conjecture for non-simply connected triangulated manifolds.     

On characterizations of distributions by mean absolute deviation and variance bounds

In this paper we present a bound for the mean absolute deviation of an arbitrary real-valued function of a discrete random variable. Using this bound we characterize a mixture of two Waring (hence geometric) distributions by linearity of a function involved in the bound. A double Lomax distribution is characterized by linearity of the same function involved in the analogous bound for a continuous distribution. Finally, we characterize the Pearson system of distributions and the generalized hypergeometric distributions by a quadratic function involved in a similar bound for the variance of a function of a random variable.     

Ricci curvature and betti numbers

We derive a uniform bound for the total betti number of a closed manifold in terms of a Ricci curvature lower bound, a conjugate radius lower bound and a diameter upper bound. The result is based on an angle version of Toponogov comparison estimate for small triangles in a complete manifold with a Ricci curvature lower bound. We also give a uniform estimate on the generators of the fundamental group and prove a fibration theorem in this setting.     

On diagonal dominance arguments for bounding 6A-16∞

In a recent paper by J.M. Varah, an upper bound for 6A^-16_∞ was determined, under the assumption that A is strictly diagonally dominant, and this bound was then used to obtain a lower bound for the smallest singular value for A. In this note, this upper bound for 6A^-16_∞ is sharpened, and extended to a wider class of matrices. This bound is then used to obtain an improved lower bound for the smallest singular value of a matrix.     

A note on construction of upper bound graphs

In this paper, we consider construction of upper bound graphs. An upper bound graph can be transformed into a nova by contractions and a nova can be transformed into an upper bound graph by splits. These results include a characterization on upper bound graphs.