How to extract a positive definite submatrix from a PSD matrix?
$begingroup$
Let $M$ be a real symmetric positive semi-definite matrix s.t. there is only one zero eigenvalue.
Question: Is it true that there is a unique principal submatrix that is positive definite? If so, how to determine this submatrix?
First trial: Let the eigenvector corresponding to the zero eigenvalue be $v$. We can represent $M$ as
begin{equation}M=Q'DQ,tag{*}end{equation}
where $Q'Q=I$ and $D$ is a diagonal matrix. Suppose for certainty that the last element of D is equal to $0$, i.e., $d_{nn}=0$. This means that the last column of $Q$ is equal to $v$.
Now let's write $D=begin{bmatrix}D_1& 0\0& 0end{bmatrix}$ and $Q=begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}$, where $D_1$ is a PD diagonal matrix, $tilde Q$ is an $[n-1,n-1]$ matrix, $q_1$ and $q_2$ are vectors, and $x$ is a scalar.
With this, we rewrite (*) as
$$M=begin{bmatrix}tilde Q'& q_2\q_1'& xend{bmatrix}begin{bmatrix}D_1& 0\0& 0end{bmatrix}begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}=
begin{bmatrix}tilde Q'D_1& 0\q_1'D_1& 0end{bmatrix}begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}=
begin{bmatrix}tilde Q'D_1tilde Q& tilde Q'D_1q_1\q_1'D_1tilde Q& q_1'D_1q_1end{bmatrix}$$
Here, $tilde Q'D_1tilde Q$ is the $(n,n)$-principal submatrix of $M$, which is positive definite if $tilde Q$ is non-singular. Thus the problem boils down to deternining non-singular principal submatrices of $Q$. However, I'm not sure is this makes the problem any simpler..
Solution (?): The number of PD principal submatrices id equal to the number of non-zero elements in the eigenvector $v$. If $v_ineq 0$, $M[i]$ is PD.
I will post the proof in a day or so.
matrices
asked Jan 11 at 14:45
DmitryDmitry
657518
$endgroup$
add a comment |
$begingroup$
Let $M$ be a real symmetric positive semi-definite matrix s.t. there is only one zero eigenvalue.
Question: Is it true that there is a unique principal submatrix that is positive definite? If so, how to determine this submatrix?
First trial: Let the eigenvector corresponding to the zero eigenvalue be $v$. We can represent $M$ as
begin{equation}M=Q'DQ,tag{*}end{equation}
where $Q'Q=I$ and $D$ is a diagonal matrix. Suppose for certainty that the last element of D is equal to $0$, i.e., $d_{nn}=0$. This means that the last column of $Q$ is equal to $v$.
Now let's write $D=begin{bmatrix}D_1& 0\0& 0end{bmatrix}$ and $Q=begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}$, where $D_1$ is a PD diagonal matrix, $tilde Q$ is an $[n-1,n-1]$ matrix, $q_1$ and $q_2$ are vectors, and $x$ is a scalar.
With this, we rewrite (*) as
$$M=begin{bmatrix}tilde Q'& q_2\q_1'& xend{bmatrix}begin{bmatrix}D_1& 0\0& 0end{bmatrix}begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}=
begin{bmatrix}tilde Q'D_1& 0\q_1'D_1& 0end{bmatrix}begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}=
begin{bmatrix}tilde Q'D_1tilde Q& tilde Q'D_1q_1\q_1'D_1tilde Q& q_1'D_1q_1end{bmatrix}$$
Here, $tilde Q'D_1tilde Q$ is the $(n,n)$-principal submatrix of $M$, which is positive definite if $tilde Q$ is non-singular. Thus the problem boils down to deternining non-singular principal submatrices of $Q$. However, I'm not sure is this makes the problem any simpler..
Solution (?): The number of PD principal submatrices id equal to the number of non-zero elements in the eigenvector $v$. If $v_ineq 0$, $M[i]$ is PD.
I will post the proof in a day or so.
matrices
asked Jan 11 at 14:45
DmitryDmitry
657518
$endgroup$
1
$begingroup$
You can extract principal submatrices using "elimination matrices"
$endgroup$
– Bertrand
Jan 11 at 14:54
$begingroup$
@Bertrand, I know how to extract submatrices. The question is rather which one is to extract?
$endgroup$
– Dmitry
Jan 11 at 15:02
add a comment |
$begingroup$
Let $M$ be a real symmetric positive semi-definite matrix s.t. there is only one zero eigenvalue.
Question: Is it true that there is a unique principal submatrix that is positive definite? If so, how to determine this submatrix?
First trial: Let the eigenvector corresponding to the zero eigenvalue be $v$. We can represent $M$ as
begin{equation}M=Q'DQ,tag{*}end{equation}
where $Q'Q=I$ and $D$ is a diagonal matrix. Suppose for certainty that the last element of D is equal to $0$, i.e., $d_{nn}=0$. This means that the last column of $Q$ is equal to $v$.
Now let's write $D=begin{bmatrix}D_1& 0\0& 0end{bmatrix}$ and $Q=begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}$, where $D_1$ is a PD diagonal matrix, $tilde Q$ is an $[n-1,n-1]$ matrix, $q_1$ and $q_2$ are vectors, and $x$ is a scalar.
With this, we rewrite (*) as
$$M=begin{bmatrix}tilde Q'& q_2\q_1'& xend{bmatrix}begin{bmatrix}D_1& 0\0& 0end{bmatrix}begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}=
begin{bmatrix}tilde Q'D_1& 0\q_1'D_1& 0end{bmatrix}begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}=
begin{bmatrix}tilde Q'D_1tilde Q& tilde Q'D_1q_1\q_1'D_1tilde Q& q_1'D_1q_1end{bmatrix}$$
Here, $tilde Q'D_1tilde Q$ is the $(n,n)$-principal submatrix of $M$, which is positive definite if $tilde Q$ is non-singular. Thus the problem boils down to deternining non-singular principal submatrices of $Q$. However, I'm not sure is this makes the problem any simpler..
Solution (?): The number of PD principal submatrices id equal to the number of non-zero elements in the eigenvector $v$. If $v_ineq 0$, $M[i]$ is PD.
I will post the proof in a day or so.
matrices
asked Jan 11 at 14:45
DmitryDmitry
657518
$endgroup$
Let $M$ be a real symmetric positive semi-definite matrix s.t. there is only one zero eigenvalue.
Question: Is it true that there is a unique principal submatrix that is positive definite? If so, how to determine this submatrix?
First trial: Let the eigenvector corresponding to the zero eigenvalue be $v$. We can represent $M$ as
begin{equation}M=Q'DQ,tag{*}end{equation}
where $Q'Q=I$ and $D$ is a diagonal matrix. Suppose for certainty that the last element of D is equal to $0$, i.e., $d_{nn}=0$. This means that the last column of $Q$ is equal to $v$.
Now let's write $D=begin{bmatrix}D_1& 0\0& 0end{bmatrix}$ and $Q=begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}$, where $D_1$ is a PD diagonal matrix, $tilde Q$ is an $[n-1,n-1]$ matrix, $q_1$ and $q_2$ are vectors, and $x$ is a scalar.
With this, we rewrite (*) as
$$M=begin{bmatrix}tilde Q'& q_2\q_1'& xend{bmatrix}begin{bmatrix}D_1& 0\0& 0end{bmatrix}begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}=
begin{bmatrix}tilde Q'D_1& 0\q_1'D_1& 0end{bmatrix}begin{bmatrix}tilde Q& q_1\q_2'& xend{bmatrix}=
begin{bmatrix}tilde Q'D_1tilde Q& tilde Q'D_1q_1\q_1'D_1tilde Q& q_1'D_1q_1end{bmatrix}$$
Here, $tilde Q'D_1tilde Q$ is the $(n,n)$-principal submatrix of $M$, which is positive definite if $tilde Q$ is non-singular. Thus the problem boils down to deternining non-singular principal submatrices of $Q$. However, I'm not sure is this makes the problem any simpler..
Solution (?): The number of PD principal submatrices id equal to the number of non-zero elements in the eigenvector $v$. If $v_ineq 0$, $M[i]$ is PD.
I will post the proof in a day or so.
matrices
matrices
asked Jan 11 at 14:45
DmitryDmitry
657518
asked Jan 11 at 14:45
DmitryDmitry
657518
edited Jan 16 at 10:04
Dmitry
asked Jan 11 at 14:45
DmitryDmitry
657518
asked Jan 11 at 14:45
DmitryDmitry
657518
asked Jan 11 at 14:45
DmitryDmitry
657518
657518
1
$begingroup$
You can extract principal submatrices using "elimination matrices"
$endgroup$
– Bertrand
Jan 11 at 14:54
$begingroup$
@Bertrand, I know how to extract submatrices. The question is rather which one is to extract?
$endgroup$
– Dmitry
Jan 11 at 15:02
add a comment |
1
$begingroup$
You can extract principal submatrices using "elimination matrices"
$endgroup$
– Bertrand
Jan 11 at 14:54
$begingroup$
@Bertrand, I know how to extract submatrices. The question is rather which one is to extract?
$endgroup$
– Dmitry
Jan 11 at 15:02
1
1
$begingroup$
You can extract principal submatrices using "elimination matrices"
$endgroup$
– Bertrand
Jan 11 at 14:54
$begingroup$
You can extract principal submatrices using "elimination matrices"
$endgroup$
– Bertrand
Jan 11 at 14:54
$begingroup$
@Bertrand, I know how to extract submatrices. The question is rather which one is to extract?
$endgroup$
– Dmitry
Jan 11 at 15:02
$begingroup$
@Bertrand, I know how to extract submatrices. The question is rather which one is to extract?
$endgroup$
– Dmitry
Jan 11 at 15:02
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This result stated for instance by Moschini may be useful:
Lemma. Let $S$ be an $n times n$ symmetric matrix that satisfies $Sp = 0$, where $p ne 0$, and let $tilde{S}$ be an $(n-1) times (n-1)$ matrix obtained from $S$ by deleting any one row and the corresponding column. Then a necessary and sufficient condition
for $S$ to be negative semidefinite is that $tilde{S}$ is negative semidefinite.
Moschini, G., 1999, "Imposing Local Curvature Conditions in Flexible Demand Systems," Journal of Business & Economic Statistics, 17, 487-490.
answered Jan 11 at 15:04
BertrandBertrand
964
$endgroup$
$begingroup$
Shouldn't it read: "... is that $tilde S$ is negative definite"? Otherwise I'm not sure that this statement is true. Anyway, this does not solve my problem.
$endgroup$
– Dmitry
Jan 11 at 15:17
$begingroup$
It is negative semidefinite, and not negative definite. The reason is clear in the proof. The lemma does not apply to diagonal matrices, as diagonal matrices do not satisfy $Sp = 0$ for $p ne 0$.
$endgroup$
– Bertrand
Jan 11 at 16:38
add a comment |
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%2f3069915%2fhow-to-extract-a-positive-definite-submatrix-from-a-psd-matrix%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This result stated for instance by Moschini may be useful:
Lemma. Let $S$ be an $n times n$ symmetric matrix that satisfies $Sp = 0$, where $p ne 0$, and let $tilde{S}$ be an $(n-1) times (n-1)$ matrix obtained from $S$ by deleting any one row and the corresponding column. Then a necessary and sufficient condition
for $S$ to be negative semidefinite is that $tilde{S}$ is negative semidefinite.
Moschini, G., 1999, "Imposing Local Curvature Conditions in Flexible Demand Systems," Journal of Business & Economic Statistics, 17, 487-490.
answered Jan 11 at 15:04
BertrandBertrand
964
$endgroup$
$begingroup$
Shouldn't it read: "... is that $tilde S$ is negative definite"? Otherwise I'm not sure that this statement is true. Anyway, this does not solve my problem.
$endgroup$
– Dmitry
Jan 11 at 15:17
$begingroup$
It is negative semidefinite, and not negative definite. The reason is clear in the proof. The lemma does not apply to diagonal matrices, as diagonal matrices do not satisfy $Sp = 0$ for $p ne 0$.
$endgroup$
– Bertrand
Jan 11 at 16:38
add a comment |
$begingroup$
This result stated for instance by Moschini may be useful:
Lemma. Let $S$ be an $n times n$ symmetric matrix that satisfies $Sp = 0$, where $p ne 0$, and let $tilde{S}$ be an $(n-1) times (n-1)$ matrix obtained from $S$ by deleting any one row and the corresponding column. Then a necessary and sufficient condition
for $S$ to be negative semidefinite is that $tilde{S}$ is negative semidefinite.
Moschini, G., 1999, "Imposing Local Curvature Conditions in Flexible Demand Systems," Journal of Business & Economic Statistics, 17, 487-490.
answered Jan 11 at 15:04
BertrandBertrand
964
$endgroup$
$begingroup$
Shouldn't it read: "... is that $tilde S$ is negative definite"? Otherwise I'm not sure that this statement is true. Anyway, this does not solve my problem.
$endgroup$
– Dmitry
Jan 11 at 15:17
$begingroup$
It is negative semidefinite, and not negative definite. The reason is clear in the proof. The lemma does not apply to diagonal matrices, as diagonal matrices do not satisfy $Sp = 0$ for $p ne 0$.
$endgroup$
– Bertrand
Jan 11 at 16:38
add a comment |
$begingroup$
This result stated for instance by Moschini may be useful:
Lemma. Let $S$ be an $n times n$ symmetric matrix that satisfies $Sp = 0$, where $p ne 0$, and let $tilde{S}$ be an $(n-1) times (n-1)$ matrix obtained from $S$ by deleting any one row and the corresponding column. Then a necessary and sufficient condition
for $S$ to be negative semidefinite is that $tilde{S}$ is negative semidefinite.
Moschini, G., 1999, "Imposing Local Curvature Conditions in Flexible Demand Systems," Journal of Business & Economic Statistics, 17, 487-490.
answered Jan 11 at 15:04
BertrandBertrand
964
$endgroup$
This result stated for instance by Moschini may be useful:
Lemma. Let $S$ be an $n times n$ symmetric matrix that satisfies $Sp = 0$, where $p ne 0$, and let $tilde{S}$ be an $(n-1) times (n-1)$ matrix obtained from $S$ by deleting any one row and the corresponding column. Then a necessary and sufficient condition
for $S$ to be negative semidefinite is that $tilde{S}$ is negative semidefinite.
Moschini, G., 1999, "Imposing Local Curvature Conditions in Flexible Demand Systems," Journal of Business & Economic Statistics, 17, 487-490.
answered Jan 11 at 15:04
BertrandBertrand
964
answered Jan 11 at 15:04
BertrandBertrand
964
answered Jan 11 at 15:04
BertrandBertrand
964
answered Jan 11 at 15:04
BertrandBertrand
964
964
$begingroup$
Shouldn't it read: "... is that $tilde S$ is negative definite"? Otherwise I'm not sure that this statement is true. Anyway, this does not solve my problem.
$endgroup$
– Dmitry
Jan 11 at 15:17
$begingroup$
It is negative semidefinite, and not negative definite. The reason is clear in the proof. The lemma does not apply to diagonal matrices, as diagonal matrices do not satisfy $Sp = 0$ for $p ne 0$.
$endgroup$
– Bertrand
Jan 11 at 16:38
add a comment |
$begingroup$
Shouldn't it read: "... is that $tilde S$ is negative definite"? Otherwise I'm not sure that this statement is true. Anyway, this does not solve my problem.
$endgroup$
– Dmitry
Jan 11 at 15:17
$begingroup$
It is negative semidefinite, and not negative definite. The reason is clear in the proof. The lemma does not apply to diagonal matrices, as diagonal matrices do not satisfy $Sp = 0$ for $p ne 0$.
$endgroup$
– Bertrand
Jan 11 at 16:38
$begingroup$
Shouldn't it read: "... is that $tilde S$ is negative definite"? Otherwise I'm not sure that this statement is true. Anyway, this does not solve my problem.
$endgroup$
– Dmitry
Jan 11 at 15:17
$begingroup$
Shouldn't it read: "... is that $tilde S$ is negative definite"? Otherwise I'm not sure that this statement is true. Anyway, this does not solve my problem.
$endgroup$
– Dmitry
Jan 11 at 15:17
$begingroup$
It is negative semidefinite, and not negative definite. The reason is clear in the proof. The lemma does not apply to diagonal matrices, as diagonal matrices do not satisfy $Sp = 0$ for $p ne 0$.
$endgroup$
– Bertrand
Jan 11 at 16:38
$begingroup$
It is negative semidefinite, and not negative definite. The reason is clear in the proof. The lemma does not apply to diagonal matrices, as diagonal matrices do not satisfy $Sp = 0$ for $p ne 0$.
$endgroup$
– Bertrand
Jan 11 at 16:38
add a comment |
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.
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%2f3069915%2fhow-to-extract-a-positive-definite-submatrix-from-a-psd-matrix%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
1
$begingroup$
You can extract principal submatrices using "elimination matrices"
$endgroup$
– Bertrand
Jan 11 at 14:54
$begingroup$
@Bertrand, I know how to extract submatrices. The question is rather which one is to extract?
$endgroup$
– Dmitry
Jan 11 at 15:02