Deriving Weyl's inequality from Courant-Fischer
I'm reading Horn and Johnson's Matrix Analysis which presents a proof of Weyl's theorem that seems to be completely independent of Courant-Fischer. One of the exercises my teacher proposed is essentially to prove Weyl's theorem and he suggested using Courant-Fischer. Here's the exercise:
suppose $A,E in mathbb{C}^{ntimes n}$ are hermitian with eigenvalues $lambda_1 geq cdotsgeq lambda_n$, $epsilon_1geqcdotsgeqepsilon_n$ respectively, and $B=A+E$ has eigenvalues $mu_1geqcdotsgeqmu_n$. Prove that $lambda_i + epsilon_1 geq mu_i geq lambda_i + epsilon_n$
My attempted proof goes as such:
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}v^*(A+E)v=max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}(v^*Av+v^*Ev)$$
since the minimum of a sum is greater than the sum of the minimums, we have
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}(v^*Av+v^*Ev)geqmax_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathcal{V}\ Vert v Vert=1}v^*Evright)$$
then we can claim that the minimum of $v^*Ev$ on $mathcal{V}$ is greater than the minimum of $v^*Ev$ on $mathbb{C}^{ntimes 1}$, so we get
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathcal{V}\ Vert v Vert=1}v^*Evright)geqmax_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathbb{C}^{ntimes 1}\ Vert v Vert=1}v^*Evright)$$
but the second minimum is $epsilon_n$ by Rayleigh's theorem, so we're left with
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+epsilon_nright)=lambda_i + epsilon_n$$
which is the second inequality in the exercise. I suspect the other one can be obtained by an analogous argument. Sorry for the heavy notation, but is my argument correct? I feel it might have a hole somewhere.
linear-algebra matrices proof-verification
edited Nov 28 '18 at 19:58
user1551
71.5k566125
asked Nov 28 '18 at 19:41
AstlyDichrar
39818
add a comment |
I'm reading Horn and Johnson's Matrix Analysis which presents a proof of Weyl's theorem that seems to be completely independent of Courant-Fischer. One of the exercises my teacher proposed is essentially to prove Weyl's theorem and he suggested using Courant-Fischer. Here's the exercise:
suppose $A,E in mathbb{C}^{ntimes n}$ are hermitian with eigenvalues $lambda_1 geq cdotsgeq lambda_n$, $epsilon_1geqcdotsgeqepsilon_n$ respectively, and $B=A+E$ has eigenvalues $mu_1geqcdotsgeqmu_n$. Prove that $lambda_i + epsilon_1 geq mu_i geq lambda_i + epsilon_n$
My attempted proof goes as such:
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}v^*(A+E)v=max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}(v^*Av+v^*Ev)$$
since the minimum of a sum is greater than the sum of the minimums, we have
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}(v^*Av+v^*Ev)geqmax_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathcal{V}\ Vert v Vert=1}v^*Evright)$$
then we can claim that the minimum of $v^*Ev$ on $mathcal{V}$ is greater than the minimum of $v^*Ev$ on $mathbb{C}^{ntimes 1}$, so we get
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathcal{V}\ Vert v Vert=1}v^*Evright)geqmax_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathbb{C}^{ntimes 1}\ Vert v Vert=1}v^*Evright)$$
but the second minimum is $epsilon_n$ by Rayleigh's theorem, so we're left with
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+epsilon_nright)=lambda_i + epsilon_n$$
which is the second inequality in the exercise. I suspect the other one can be obtained by an analogous argument. Sorry for the heavy notation, but is my argument correct? I feel it might have a hole somewhere.
linear-algebra matrices proof-verification
edited Nov 28 '18 at 19:58
user1551
71.5k566125
asked Nov 28 '18 at 19:41
AstlyDichrar
39818
Your proof looks good to me, but in my copy of Horn and Johnson (1/e), the authors did use Courant-Fischer minimax principle to prove Weyl's inequality (theorem 4.3.1).
– user1551
Nov 28 '18 at 21:21
I have the second edition, and they never explicitly use 4.2.6 to 4.2.9 (which is C-F and its intermediate results in this edition), just the preceding results. It seems to simplify the proof quite a bit, at the cost of heavy notation.
– AstlyDichrar
Nov 28 '18 at 22:20
add a comment |
I'm reading Horn and Johnson's Matrix Analysis which presents a proof of Weyl's theorem that seems to be completely independent of Courant-Fischer. One of the exercises my teacher proposed is essentially to prove Weyl's theorem and he suggested using Courant-Fischer. Here's the exercise:
suppose $A,E in mathbb{C}^{ntimes n}$ are hermitian with eigenvalues $lambda_1 geq cdotsgeq lambda_n$, $epsilon_1geqcdotsgeqepsilon_n$ respectively, and $B=A+E$ has eigenvalues $mu_1geqcdotsgeqmu_n$. Prove that $lambda_i + epsilon_1 geq mu_i geq lambda_i + epsilon_n$
My attempted proof goes as such:
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}v^*(A+E)v=max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}(v^*Av+v^*Ev)$$
since the minimum of a sum is greater than the sum of the minimums, we have
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}(v^*Av+v^*Ev)geqmax_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathcal{V}\ Vert v Vert=1}v^*Evright)$$
then we can claim that the minimum of $v^*Ev$ on $mathcal{V}$ is greater than the minimum of $v^*Ev$ on $mathbb{C}^{ntimes 1}$, so we get
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathcal{V}\ Vert v Vert=1}v^*Evright)geqmax_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathbb{C}^{ntimes 1}\ Vert v Vert=1}v^*Evright)$$
but the second minimum is $epsilon_n$ by Rayleigh's theorem, so we're left with
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+epsilon_nright)=lambda_i + epsilon_n$$
which is the second inequality in the exercise. I suspect the other one can be obtained by an analogous argument. Sorry for the heavy notation, but is my argument correct? I feel it might have a hole somewhere.
linear-algebra matrices proof-verification
edited Nov 28 '18 at 19:58
user1551
71.5k566125
asked Nov 28 '18 at 19:41
AstlyDichrar
39818
I'm reading Horn and Johnson's Matrix Analysis which presents a proof of Weyl's theorem that seems to be completely independent of Courant-Fischer. One of the exercises my teacher proposed is essentially to prove Weyl's theorem and he suggested using Courant-Fischer. Here's the exercise:
suppose $A,E in mathbb{C}^{ntimes n}$ are hermitian with eigenvalues $lambda_1 geq cdotsgeq lambda_n$, $epsilon_1geqcdotsgeqepsilon_n$ respectively, and $B=A+E$ has eigenvalues $mu_1geqcdotsgeqmu_n$. Prove that $lambda_i + epsilon_1 geq mu_i geq lambda_i + epsilon_n$
My attempted proof goes as such:
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}v^*(A+E)v=max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}(v^*Av+v^*Ev)$$
since the minimum of a sum is greater than the sum of the minimums, we have
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} min_{vinmathcal{V}\ Vert v Vert=1}(v^*Av+v^*Ev)geqmax_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathcal{V}\ Vert v Vert=1}v^*Evright)$$
then we can claim that the minimum of $v^*Ev$ on $mathcal{V}$ is greater than the minimum of $v^*Ev$ on $mathbb{C}^{ntimes 1}$, so we get
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathcal{V}\ Vert v Vert=1}v^*Evright)geqmax_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+min_{vinmathbb{C}^{ntimes 1}\ Vert v Vert=1}v^*Evright)$$
but the second minimum is $epsilon_n$ by Rayleigh's theorem, so we're left with
$$max_{mathcal{V}leqmathbb{C}^{ntimes n}\ dim(mathcal{V})=i} left(min_{vinmathcal{V}\ Vert v Vert=1}v^*Av+epsilon_nright)=lambda_i + epsilon_n$$
which is the second inequality in the exercise. I suspect the other one can be obtained by an analogous argument. Sorry for the heavy notation, but is my argument correct? I feel it might have a hole somewhere.
linear-algebra matrices proof-verification
linear-algebra matrices proof-verification
edited Nov 28 '18 at 19:58
user1551
71.5k566125
asked Nov 28 '18 at 19:41
AstlyDichrar
39818
edited Nov 28 '18 at 19:58
user1551
71.5k566125
asked Nov 28 '18 at 19:41
AstlyDichrar
39818
edited Nov 28 '18 at 19:58
user1551
71.5k566125
edited Nov 28 '18 at 19:58
user1551
71.5k566125
edited Nov 28 '18 at 19:58
user1551
71.5k566125
71.5k566125
asked Nov 28 '18 at 19:41
AstlyDichrar
39818
asked Nov 28 '18 at 19:41
AstlyDichrar
39818
asked Nov 28 '18 at 19:41
AstlyDichrar
39818
39818
Your proof looks good to me, but in my copy of Horn and Johnson (1/e), the authors did use Courant-Fischer minimax principle to prove Weyl's inequality (theorem 4.3.1).
– user1551
Nov 28 '18 at 21:21
I have the second edition, and they never explicitly use 4.2.6 to 4.2.9 (which is C-F and its intermediate results in this edition), just the preceding results. It seems to simplify the proof quite a bit, at the cost of heavy notation.
– AstlyDichrar
Nov 28 '18 at 22:20
add a comment |
Your proof looks good to me, but in my copy of Horn and Johnson (1/e), the authors did use Courant-Fischer minimax principle to prove Weyl's inequality (theorem 4.3.1).
– user1551
Nov 28 '18 at 21:21
I have the second edition, and they never explicitly use 4.2.6 to 4.2.9 (which is C-F and its intermediate results in this edition), just the preceding results. It seems to simplify the proof quite a bit, at the cost of heavy notation.
– AstlyDichrar
Nov 28 '18 at 22:20
Your proof looks good to me, but in my copy of Horn and Johnson (1/e), the authors did use Courant-Fischer minimax principle to prove Weyl's inequality (theorem 4.3.1).
– user1551
Nov 28 '18 at 21:21
Your proof looks good to me, but in my copy of Horn and Johnson (1/e), the authors did use Courant-Fischer minimax principle to prove Weyl's inequality (theorem 4.3.1).
– user1551
Nov 28 '18 at 21:21
I have the second edition, and they never explicitly use 4.2.6 to 4.2.9 (which is C-F and its intermediate results in this edition), just the preceding results. It seems to simplify the proof quite a bit, at the cost of heavy notation.
– AstlyDichrar
Nov 28 '18 at 22:20
I have the second edition, and they never explicitly use 4.2.6 to 4.2.9 (which is C-F and its intermediate results in this edition), just the preceding results. It seems to simplify the proof quite a bit, at the cost of heavy notation.
– AstlyDichrar
Nov 28 '18 at 22:20
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3017592%2fderiving-weyls-inequality-from-courant-fischer%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3017592%2fderiving-weyls-inequality-from-courant-fischer%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Your proof looks good to me, but in my copy of Horn and Johnson (1/e), the authors did use Courant-Fischer minimax principle to prove Weyl's inequality (theorem 4.3.1).
– user1551
Nov 28 '18 at 21:21
I have the second edition, and they never explicitly use 4.2.6 to 4.2.9 (which is C-F and its intermediate results in this edition), just the preceding results. It seems to simplify the proof quite a bit, at the cost of heavy notation.
– AstlyDichrar
Nov 28 '18 at 22:20