Invertibility of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$?












1












$begingroup$


I'm given a problem:



$sigma_1 geq sigma_2 geq ... geq sigma_r$ are the nonzero singular values of $textbf{A}inmathbb{R}^{Mtimes N}$. If $epsilon neq 0$ is a real scalar, s.t. $|epsilon| < sigma^{2}_r$, show that $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible.



I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + epsilon I$, where $A$ is invertible



But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $textbf{A}^Ttextbf{A}$ is invertible by definition, but I'm not sure if I can just plug $textbf{A}^Ttextbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.



Can anyone help me understand WHY $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
    $endgroup$
    – qbert
    Dec 5 '18 at 21:59
















1












$begingroup$


I'm given a problem:



$sigma_1 geq sigma_2 geq ... geq sigma_r$ are the nonzero singular values of $textbf{A}inmathbb{R}^{Mtimes N}$. If $epsilon neq 0$ is a real scalar, s.t. $|epsilon| < sigma^{2}_r$, show that $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible.



I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + epsilon I$, where $A$ is invertible



But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $textbf{A}^Ttextbf{A}$ is invertible by definition, but I'm not sure if I can just plug $textbf{A}^Ttextbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.



Can anyone help me understand WHY $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
    $endgroup$
    – qbert
    Dec 5 '18 at 21:59














1












1








1





$begingroup$


I'm given a problem:



$sigma_1 geq sigma_2 geq ... geq sigma_r$ are the nonzero singular values of $textbf{A}inmathbb{R}^{Mtimes N}$. If $epsilon neq 0$ is a real scalar, s.t. $|epsilon| < sigma^{2}_r$, show that $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible.



I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + epsilon I$, where $A$ is invertible



But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $textbf{A}^Ttextbf{A}$ is invertible by definition, but I'm not sure if I can just plug $textbf{A}^Ttextbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.



Can anyone help me understand WHY $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?










share|cite|improve this question











$endgroup$




I'm given a problem:



$sigma_1 geq sigma_2 geq ... geq sigma_r$ are the nonzero singular values of $textbf{A}inmathbb{R}^{Mtimes N}$. If $epsilon neq 0$ is a real scalar, s.t. $|epsilon| < sigma^{2}_r$, show that $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible.



I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + epsilon I$, where $A$ is invertible



But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $textbf{A}^Ttextbf{A}$ is invertible by definition, but I'm not sure if I can just plug $textbf{A}^Ttextbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.



Can anyone help me understand WHY $(textbf{A}^Ttextbf{A}+epsilon textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?







linear-algebra inverse






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 6 '18 at 8:20









Tommi Brander

956922




956922










asked Dec 5 '18 at 21:24









W. MacTurkW. MacTurk

135




135












  • $begingroup$
    Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
    $endgroup$
    – qbert
    Dec 5 '18 at 21:59


















  • $begingroup$
    Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
    $endgroup$
    – qbert
    Dec 5 '18 at 21:59
















$begingroup$
Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
$endgroup$
– qbert
Dec 5 '18 at 21:59




$begingroup$
Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis
$endgroup$
– qbert
Dec 5 '18 at 21:59










2 Answers
2






active

oldest

votes


















2












$begingroup$

Write out $A$ in its SVD, $A=USigma V^T$. Then we have



$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    You moved the transpose in the last step.
    $endgroup$
    – Ian
    Dec 5 '18 at 21:49










  • $begingroup$
    Thanks. Fixed..
    $endgroup$
    – whpowell96
    Dec 5 '18 at 21:51










  • $begingroup$
    Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
    $endgroup$
    – W. MacTurk
    Dec 6 '18 at 1:58



















1












$begingroup$

You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).



[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]



Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
    $endgroup$
    – W. MacTurk
    Dec 7 '18 at 3:24











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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3027674%2finvertibility-of-textbfat-textbfa-epsilon-textbfi%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









2












$begingroup$

Write out $A$ in its SVD, $A=USigma V^T$. Then we have



$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    You moved the transpose in the last step.
    $endgroup$
    – Ian
    Dec 5 '18 at 21:49










  • $begingroup$
    Thanks. Fixed..
    $endgroup$
    – whpowell96
    Dec 5 '18 at 21:51










  • $begingroup$
    Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
    $endgroup$
    – W. MacTurk
    Dec 6 '18 at 1:58
















2












$begingroup$

Write out $A$ in its SVD, $A=USigma V^T$. Then we have



$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    You moved the transpose in the last step.
    $endgroup$
    – Ian
    Dec 5 '18 at 21:49










  • $begingroup$
    Thanks. Fixed..
    $endgroup$
    – whpowell96
    Dec 5 '18 at 21:51










  • $begingroup$
    Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
    $endgroup$
    – W. MacTurk
    Dec 6 '18 at 1:58














2












2








2





$begingroup$

Write out $A$ in its SVD, $A=USigma V^T$. Then we have



$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.






share|cite|improve this answer











$endgroup$



Write out $A$ in its SVD, $A=USigma V^T$. Then we have



$$A^TA+epsilon I = VSigma^2 V^T+epsilon I = VSigma^2V^T+epsilon VV^T = V(Sigma^2+epsilon I)V^T.$$
From this, we have that the eigenvalues are exactly $sigma_i^2+epsilon$ for $i=1dots r$ and $epsilon$ for $i=r+1dots n$. These are all nonzero, so the matrix is invertible.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 5 '18 at 21:51

























answered Dec 5 '18 at 21:47









whpowell96whpowell96

56615




56615












  • $begingroup$
    You moved the transpose in the last step.
    $endgroup$
    – Ian
    Dec 5 '18 at 21:49










  • $begingroup$
    Thanks. Fixed..
    $endgroup$
    – whpowell96
    Dec 5 '18 at 21:51










  • $begingroup$
    Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
    $endgroup$
    – W. MacTurk
    Dec 6 '18 at 1:58


















  • $begingroup$
    You moved the transpose in the last step.
    $endgroup$
    – Ian
    Dec 5 '18 at 21:49










  • $begingroup$
    Thanks. Fixed..
    $endgroup$
    – whpowell96
    Dec 5 '18 at 21:51










  • $begingroup$
    Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
    $endgroup$
    – W. MacTurk
    Dec 6 '18 at 1:58
















$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49




$begingroup$
You moved the transpose in the last step.
$endgroup$
– Ian
Dec 5 '18 at 21:49












$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51




$begingroup$
Thanks. Fixed..
$endgroup$
– whpowell96
Dec 5 '18 at 21:51












$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58




$begingroup$
Thank you! Is there a straightforward way to find the limit of $(textbf{A}^Ttextbf{A}+epsilon textbf{I})^{−1}textbf{A}^T$ as $epsilon$ goes to 0? Obviously this reduces to $(textbf{A}^Ttextbf{A})^{-1}textbf{A}^T$, but I'm not sure where to go from here without specific values for A
$endgroup$
– W. MacTurk
Dec 6 '18 at 1:58











1












$begingroup$

You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).



[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]



Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
    $endgroup$
    – W. MacTurk
    Dec 7 '18 at 3:24
















1












$begingroup$

You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).



[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]



Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
    $endgroup$
    – W. MacTurk
    Dec 7 '18 at 3:24














1












1








1





$begingroup$

You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).



[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]



Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?






share|cite|improve this answer









$endgroup$



You can show that $A^top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $sigma_1^2, ldots, sigma_r^2, 0, ldots, 0$).



[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]



Knowing this fact about $A^top A$, can you explicitly write down the eigenvalues of $A^top A + epsilon I$? What values of $epsilon$ make this matrix invertible or non-invertible?







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Dec 5 '18 at 21:45









angryavianangryavian

40.6k23380




40.6k23380












  • $begingroup$
    Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
    $endgroup$
    – W. MacTurk
    Dec 7 '18 at 3:24


















  • $begingroup$
    Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
    $endgroup$
    – W. MacTurk
    Dec 7 '18 at 3:24
















$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24




$begingroup$
Wouldn't the eigenvalues just be $sigma_{1}^{2}+epsilon , sigma_{2}^{2}+epsilon , ...sigma_{r}^{2}+epsilon$, with trailing eigenvalues of $epsilon$ if $textbf{A}^Ttextbf{A}$ was not invertible?
$endgroup$
– W. MacTurk
Dec 7 '18 at 3:24


















draft saved

draft discarded




















































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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3027674%2finvertibility-of-textbfat-textbfa-epsilon-textbfi%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

Le Mesnil-Réaume

Bundesstraße 106

Ida-Boy-Ed-Garten