Exceptions to special case of binomial inverse theorem involving $(A-B)^{-1}$?
$begingroup$
Under the Woodbury matrix identity page on Wikipedia, there is a special case under the binomial inverse section where $$(A-B)^{-1}=sum_{k=0}^infty (A^{-1}B)^{k}A^{-1}label{a}tag{1}$$
In my case, I was trying to apply it where $A=I$, which I believe simplifies nicely to $$=sum_{k=0}^infty B^klabel{b}tag{2}$$
At first, it seemed to work fine, but when testing it with random data sets, I started get obscenely large numbers in the resulting matrix. A simple case of when it seems to fail consistently is when the values of the square matrix $B$ are in the interval $[1,infty)$. At that point, the simplification seems to lead all elements of the result to infinity as $k$ goes to infinity, which when summed together, is clearly is not the inverse.
I am able to verify this in code (using R) just generating random values for $B$. I can solve for the inverse of $(I-Q)$ using built in functions and confirm the results by multiplying it by $(I-Q)$ to get $I$, but when I try to manually calculate using $ref{b}$ it falls apart.
Are there exceptions or rules somewhere for $ref{a}$ that I'm missing and inadvertently violating?
linear-algebra matrices
asked Dec 20 '18 at 16:09
anjamaanjama
233
$endgroup$
add a comment |
$begingroup$
Under the Woodbury matrix identity page on Wikipedia, there is a special case under the binomial inverse section where $$(A-B)^{-1}=sum_{k=0}^infty (A^{-1}B)^{k}A^{-1}label{a}tag{1}$$
In my case, I was trying to apply it where $A=I$, which I believe simplifies nicely to $$=sum_{k=0}^infty B^klabel{b}tag{2}$$
At first, it seemed to work fine, but when testing it with random data sets, I started get obscenely large numbers in the resulting matrix. A simple case of when it seems to fail consistently is when the values of the square matrix $B$ are in the interval $[1,infty)$. At that point, the simplification seems to lead all elements of the result to infinity as $k$ goes to infinity, which when summed together, is clearly is not the inverse.
I am able to verify this in code (using R) just generating random values for $B$. I can solve for the inverse of $(I-Q)$ using built in functions and confirm the results by multiplying it by $(I-Q)$ to get $I$, but when I try to manually calculate using $ref{b}$ it falls apart.
Are there exceptions or rules somewhere for $ref{a}$ that I'm missing and inadvertently violating?
linear-algebra matrices
asked Dec 20 '18 at 16:09
anjamaanjama
233
$endgroup$
$begingroup$
You have a similar problem even with the binomial theorem over real numbers; take $(1 - 2)^{-1},$ for example, and expand it by the binomial formula.
$endgroup$
– David K
Dec 20 '18 at 16:15
$begingroup$
Check out Neumann series.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:19
$begingroup$
The infinite sum $sum_{k=0}^infty C^k$ converges if and only if $|C|<1$, so $|A^{-1}B|<1$ is a necessary condition you need for (1) to hold.
$endgroup$
– Mike Earnest
Dec 20 '18 at 16:24
1
$begingroup$
@MikeEarnest Norm bound by one is sufficient, but not necessary for convergence.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:29
add a comment |
$begingroup$
Under the Woodbury matrix identity page on Wikipedia, there is a special case under the binomial inverse section where $$(A-B)^{-1}=sum_{k=0}^infty (A^{-1}B)^{k}A^{-1}label{a}tag{1}$$
In my case, I was trying to apply it where $A=I$, which I believe simplifies nicely to $$=sum_{k=0}^infty B^klabel{b}tag{2}$$
At first, it seemed to work fine, but when testing it with random data sets, I started get obscenely large numbers in the resulting matrix. A simple case of when it seems to fail consistently is when the values of the square matrix $B$ are in the interval $[1,infty)$. At that point, the simplification seems to lead all elements of the result to infinity as $k$ goes to infinity, which when summed together, is clearly is not the inverse.
I am able to verify this in code (using R) just generating random values for $B$. I can solve for the inverse of $(I-Q)$ using built in functions and confirm the results by multiplying it by $(I-Q)$ to get $I$, but when I try to manually calculate using $ref{b}$ it falls apart.
Are there exceptions or rules somewhere for $ref{a}$ that I'm missing and inadvertently violating?
linear-algebra matrices
asked Dec 20 '18 at 16:09
anjamaanjama
233
$endgroup$
Under the Woodbury matrix identity page on Wikipedia, there is a special case under the binomial inverse section where $$(A-B)^{-1}=sum_{k=0}^infty (A^{-1}B)^{k}A^{-1}label{a}tag{1}$$
In my case, I was trying to apply it where $A=I$, which I believe simplifies nicely to $$=sum_{k=0}^infty B^klabel{b}tag{2}$$
At first, it seemed to work fine, but when testing it with random data sets, I started get obscenely large numbers in the resulting matrix. A simple case of when it seems to fail consistently is when the values of the square matrix $B$ are in the interval $[1,infty)$. At that point, the simplification seems to lead all elements of the result to infinity as $k$ goes to infinity, which when summed together, is clearly is not the inverse.
I am able to verify this in code (using R) just generating random values for $B$. I can solve for the inverse of $(I-Q)$ using built in functions and confirm the results by multiplying it by $(I-Q)$ to get $I$, but when I try to manually calculate using $ref{b}$ it falls apart.
Are there exceptions or rules somewhere for $ref{a}$ that I'm missing and inadvertently violating?
linear-algebra matrices
linear-algebra matrices
asked Dec 20 '18 at 16:09
anjamaanjama
233
asked Dec 20 '18 at 16:09
anjamaanjama
233
asked Dec 20 '18 at 16:09
anjamaanjama
233
asked Dec 20 '18 at 16:09
anjamaanjama
233
asked Dec 20 '18 at 16:09
anjamaanjama
233
233
$begingroup$
You have a similar problem even with the binomial theorem over real numbers; take $(1 - 2)^{-1},$ for example, and expand it by the binomial formula.
$endgroup$
– David K
Dec 20 '18 at 16:15
$begingroup$
Check out Neumann series.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:19
$begingroup$
The infinite sum $sum_{k=0}^infty C^k$ converges if and only if $|C|<1$, so $|A^{-1}B|<1$ is a necessary condition you need for (1) to hold.
$endgroup$
– Mike Earnest
Dec 20 '18 at 16:24
1
$begingroup$
@MikeEarnest Norm bound by one is sufficient, but not necessary for convergence.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:29
add a comment |
$begingroup$
You have a similar problem even with the binomial theorem over real numbers; take $(1 - 2)^{-1},$ for example, and expand it by the binomial formula.
$endgroup$
– David K
Dec 20 '18 at 16:15
$begingroup$
Check out Neumann series.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:19
$begingroup$
The infinite sum $sum_{k=0}^infty C^k$ converges if and only if $|C|<1$, so $|A^{-1}B|<1$ is a necessary condition you need for (1) to hold.
$endgroup$
– Mike Earnest
Dec 20 '18 at 16:24
1
$begingroup$
@MikeEarnest Norm bound by one is sufficient, but not necessary for convergence.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:29
$begingroup$
You have a similar problem even with the binomial theorem over real numbers; take $(1 - 2)^{-1},$ for example, and expand it by the binomial formula.
$endgroup$
– David K
Dec 20 '18 at 16:15
$begingroup$
You have a similar problem even with the binomial theorem over real numbers; take $(1 - 2)^{-1},$ for example, and expand it by the binomial formula.
$endgroup$
– David K
Dec 20 '18 at 16:15
$begingroup$
Check out Neumann series.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:19
$begingroup$
Check out Neumann series.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:19
$begingroup$
The infinite sum $sum_{k=0}^infty C^k$ converges if and only if $|C|<1$, so $|A^{-1}B|<1$ is a necessary condition you need for (1) to hold.
$endgroup$
– Mike Earnest
Dec 20 '18 at 16:24
$begingroup$
The infinite sum $sum_{k=0}^infty C^k$ converges if and only if $|C|<1$, so $|A^{-1}B|<1$ is a necessary condition you need for (1) to hold.
$endgroup$
– Mike Earnest
Dec 20 '18 at 16:24
1
1
$begingroup$
@MikeEarnest Norm bound by one is sufficient, but not necessary for convergence.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:29
$begingroup$
@MikeEarnest Norm bound by one is sufficient, but not necessary for convergence.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:29
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
We will indeed have $(I - B)^{-1} = sum_{k=0}^infty B^k$ whenever the sum on the right converges. This sum will converge if and only if the eigenvalues of $B$ all have magnitude strictly less than $1$.
The equation on wikipedia should have a blurb to the effect of "whenever the sum on the right converges".
A $1 times 1$ example that illustrates what's going on: note that
$$
frac 1{1-x} = 1 + x cdot frac{1}{1 - x}
$$
this equation has a "recursive structure", so we could also write
$$
frac 1{1-x} = 1 + x cdot left[1 + x cdot frac{1}{1 - x}right]\
= 1 + x + x^2 cdot frac 1{1-x}
$$
so that in general, we have
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots + x^n cdot frac 1{1-x}
$$
Now, whenever the expression on the right approaches a limit, we could also write
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots = sum_{k=0}^infty x^k
$$
this manipulation only makes sense rigorously (i.e. says something accurate in terms of the usual notion of a limit) when $|x| < 1$.
answered Dec 20 '18 at 16:31
OmnomnomnomOmnomnomnom
128k791184
$endgroup$
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%2f3047695%2fexceptions-to-special-case-of-binomial-inverse-theorem-involving-a-b-1%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$
We will indeed have $(I - B)^{-1} = sum_{k=0}^infty B^k$ whenever the sum on the right converges. This sum will converge if and only if the eigenvalues of $B$ all have magnitude strictly less than $1$.
The equation on wikipedia should have a blurb to the effect of "whenever the sum on the right converges".
A $1 times 1$ example that illustrates what's going on: note that
$$
frac 1{1-x} = 1 + x cdot frac{1}{1 - x}
$$
this equation has a "recursive structure", so we could also write
$$
frac 1{1-x} = 1 + x cdot left[1 + x cdot frac{1}{1 - x}right]\
= 1 + x + x^2 cdot frac 1{1-x}
$$
so that in general, we have
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots + x^n cdot frac 1{1-x}
$$
Now, whenever the expression on the right approaches a limit, we could also write
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots = sum_{k=0}^infty x^k
$$
this manipulation only makes sense rigorously (i.e. says something accurate in terms of the usual notion of a limit) when $|x| < 1$.
answered Dec 20 '18 at 16:31
OmnomnomnomOmnomnomnom
128k791184
$endgroup$
add a comment |
$begingroup$
We will indeed have $(I - B)^{-1} = sum_{k=0}^infty B^k$ whenever the sum on the right converges. This sum will converge if and only if the eigenvalues of $B$ all have magnitude strictly less than $1$.
The equation on wikipedia should have a blurb to the effect of "whenever the sum on the right converges".
A $1 times 1$ example that illustrates what's going on: note that
$$
frac 1{1-x} = 1 + x cdot frac{1}{1 - x}
$$
this equation has a "recursive structure", so we could also write
$$
frac 1{1-x} = 1 + x cdot left[1 + x cdot frac{1}{1 - x}right]\
= 1 + x + x^2 cdot frac 1{1-x}
$$
so that in general, we have
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots + x^n cdot frac 1{1-x}
$$
Now, whenever the expression on the right approaches a limit, we could also write
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots = sum_{k=0}^infty x^k
$$
this manipulation only makes sense rigorously (i.e. says something accurate in terms of the usual notion of a limit) when $|x| < 1$.
answered Dec 20 '18 at 16:31
OmnomnomnomOmnomnomnom
128k791184
$endgroup$
add a comment |
$begingroup$
We will indeed have $(I - B)^{-1} = sum_{k=0}^infty B^k$ whenever the sum on the right converges. This sum will converge if and only if the eigenvalues of $B$ all have magnitude strictly less than $1$.
The equation on wikipedia should have a blurb to the effect of "whenever the sum on the right converges".
A $1 times 1$ example that illustrates what's going on: note that
$$
frac 1{1-x} = 1 + x cdot frac{1}{1 - x}
$$
this equation has a "recursive structure", so we could also write
$$
frac 1{1-x} = 1 + x cdot left[1 + x cdot frac{1}{1 - x}right]\
= 1 + x + x^2 cdot frac 1{1-x}
$$
so that in general, we have
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots + x^n cdot frac 1{1-x}
$$
Now, whenever the expression on the right approaches a limit, we could also write
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots = sum_{k=0}^infty x^k
$$
this manipulation only makes sense rigorously (i.e. says something accurate in terms of the usual notion of a limit) when $|x| < 1$.
answered Dec 20 '18 at 16:31
OmnomnomnomOmnomnomnom
128k791184
$endgroup$
We will indeed have $(I - B)^{-1} = sum_{k=0}^infty B^k$ whenever the sum on the right converges. This sum will converge if and only if the eigenvalues of $B$ all have magnitude strictly less than $1$.
The equation on wikipedia should have a blurb to the effect of "whenever the sum on the right converges".
A $1 times 1$ example that illustrates what's going on: note that
$$
frac 1{1-x} = 1 + x cdot frac{1}{1 - x}
$$
this equation has a "recursive structure", so we could also write
$$
frac 1{1-x} = 1 + x cdot left[1 + x cdot frac{1}{1 - x}right]\
= 1 + x + x^2 cdot frac 1{1-x}
$$
so that in general, we have
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots + x^n cdot frac 1{1-x}
$$
Now, whenever the expression on the right approaches a limit, we could also write
$$
frac 1{1 - x} = 1 + x + x^2 + x^3 + cdots = sum_{k=0}^infty x^k
$$
this manipulation only makes sense rigorously (i.e. says something accurate in terms of the usual notion of a limit) when $|x| < 1$.
answered Dec 20 '18 at 16:31
OmnomnomnomOmnomnomnom
128k791184
answered Dec 20 '18 at 16:31
OmnomnomnomOmnomnomnom
128k791184
answered Dec 20 '18 at 16:31
OmnomnomnomOmnomnomnom
128k791184
answered Dec 20 '18 at 16:31
OmnomnomnomOmnomnomnom
128k791184
128k791184
add a comment |
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%2f3047695%2fexceptions-to-special-case-of-binomial-inverse-theorem-involving-a-b-1%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
$begingroup$
You have a similar problem even with the binomial theorem over real numbers; take $(1 - 2)^{-1},$ for example, and expand it by the binomial formula.
$endgroup$
– David K
Dec 20 '18 at 16:15
$begingroup$
Check out Neumann series.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:19
$begingroup$
The infinite sum $sum_{k=0}^infty C^k$ converges if and only if $|C|<1$, so $|A^{-1}B|<1$ is a necessary condition you need for (1) to hold.
$endgroup$
– Mike Earnest
Dec 20 '18 at 16:24
1
$begingroup$
@MikeEarnest Norm bound by one is sufficient, but not necessary for convergence.
$endgroup$
– A.Γ.
Dec 20 '18 at 16:29