Mixing
Inverse of tridiagonal Toeplitz matrix
Consider the following tridiagonal Toeplitz matrix. Let $n$ be even.
$${A_{n times n}} = left[ {begin{array}{*{20}{c}}
{0}&{1}&{}&{}&{}\
{1}&{0}&{1}&{}&{}\
{}&{1}&{ddots}&{ddots}&{}\
{}&{}&{ddots}&{ddots}&{1}\
{}&{}&{}&{1}&{0}
end{array}} right]$$
What is the inverse $A^{-1}$?
Clearly, $A^{-1}$ is symmetric.
I look for a proof of the following conjecture that $A^{-1}$ is given as follows:
If $A_{i, j}^{-1}$ such that $j$ is odd and $i =1+j + 2 m$ with $min cal N_0$, then $A_{i, j}^{-1} = (-1)^m$. From which follows by symmetry:
If $A_{i, j}^{-1}$ such that $j$ is even and $i =-1+j - 2 m$ with $min cal N_0$, then $A_{i, j}^{-1} = (-1)^m$.
All other $A_{i, j}^{-1} = 0$.
Here is an example, computed with Matlab, for $n=10$ which shows the structure:
$${A_{10 times 10}^{-1}} = left[ {begin{array}{*{20}{r}}
0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 \
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \
-1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 \
1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \
-1 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \
1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 & 0
end{array}} right]$$
linear-algebra matrices inverse symmetric-matrices
asked Nov 9 '18 at 10:47
AndreasAndreas
7,8281037
add a comment |
Consider the following tridiagonal Toeplitz matrix. Let $n$ be even.
$${A_{n times n}} = left[ {begin{array}{*{20}{c}}
{0}&{1}&{}&{}&{}\
{1}&{0}&{1}&{}&{}\
{}&{1}&{ddots}&{ddots}&{}\
{}&{}&{ddots}&{ddots}&{1}\
{}&{}&{}&{1}&{0}
end{array}} right]$$
What is the inverse $A^{-1}$?
Clearly, $A^{-1}$ is symmetric.
I look for a proof of the following conjecture that $A^{-1}$ is given as follows:
If $A_{i, j}^{-1}$ such that $j$ is odd and $i =1+j + 2 m$ with $min cal N_0$, then $A_{i, j}^{-1} = (-1)^m$. From which follows by symmetry:
If $A_{i, j}^{-1}$ such that $j$ is even and $i =-1+j - 2 m$ with $min cal N_0$, then $A_{i, j}^{-1} = (-1)^m$.
All other $A_{i, j}^{-1} = 0$.
Here is an example, computed with Matlab, for $n=10$ which shows the structure:
$${A_{10 times 10}^{-1}} = left[ {begin{array}{*{20}{r}}
0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 \
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \
-1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 \
1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \
-1 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \
1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 & 0
end{array}} right]$$
linear-algebra matrices inverse symmetric-matrices
asked Nov 9 '18 at 10:47
AndreasAndreas
7,8281037
You might try the Cayley-Hamilton theorem. $A^{-1}$ can be written as a polynomial in $A$ and with some ingenuity you may be able to figure out the coefficients.
– Richard Martin
Nov 9 '18 at 11:00
Can you give us an example for $n$ being odd too?
– Mostafa Ayaz
Nov 9 '18 at 11:24
@MostafaAyaz The questions says $n$ even. For $n$ odd, as far as I see it, $det(A)=0$ so no inverse exists. You may want to prove this as well ....
– Andreas
Nov 9 '18 at 11:27
add a comment |
Consider the following tridiagonal Toeplitz matrix. Let $n$ be even.
$${A_{n times n}} = left[ {begin{array}{*{20}{c}}
{0}&{1}&{}&{}&{}\
{1}&{0}&{1}&{}&{}\
{}&{1}&{ddots}&{ddots}&{}\
{}&{}&{ddots}&{ddots}&{1}\
{}&{}&{}&{1}&{0}
end{array}} right]$$
What is the inverse $A^{-1}$?
Clearly, $A^{-1}$ is symmetric.
I look for a proof of the following conjecture that $A^{-1}$ is given as follows:
If $A_{i, j}^{-1}$ such that $j$ is odd and $i =1+j + 2 m$ with $min cal N_0$, then $A_{i, j}^{-1} = (-1)^m$. From which follows by symmetry:
If $A_{i, j}^{-1}$ such that $j$ is even and $i =-1+j - 2 m$ with $min cal N_0$, then $A_{i, j}^{-1} = (-1)^m$.
All other $A_{i, j}^{-1} = 0$.
Here is an example, computed with Matlab, for $n=10$ which shows the structure:
$${A_{10 times 10}^{-1}} = left[ {begin{array}{*{20}{r}}
0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 \
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \
-1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 \
1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \
-1 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \
1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 & 0
end{array}} right]$$
linear-algebra matrices inverse symmetric-matrices
asked Nov 9 '18 at 10:47
AndreasAndreas
7,8281037
Consider the following tridiagonal Toeplitz matrix. Let $n$ be even.
$${A_{n times n}} = left[ {begin{array}{*{20}{c}}
{0}&{1}&{}&{}&{}\
{1}&{0}&{1}&{}&{}\
{}&{1}&{ddots}&{ddots}&{}\
{}&{}&{ddots}&{ddots}&{1}\
{}&{}&{}&{1}&{0}
end{array}} right]$$
What is the inverse $A^{-1}$?
Clearly, $A^{-1}$ is symmetric.
I look for a proof of the following conjecture that $A^{-1}$ is given as follows:
If $A_{i, j}^{-1}$ such that $j$ is odd and $i =1+j + 2 m$ with $min cal N_0$, then $A_{i, j}^{-1} = (-1)^m$. From which follows by symmetry:
If $A_{i, j}^{-1}$ such that $j$ is even and $i =-1+j - 2 m$ with $min cal N_0$, then $A_{i, j}^{-1} = (-1)^m$.
All other $A_{i, j}^{-1} = 0$.
Here is an example, computed with Matlab, for $n=10$ which shows the structure:
$${A_{10 times 10}^{-1}} = left[ {begin{array}{*{20}{r}}
0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 \
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \
-1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 \
1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \
-1 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \
1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 & 0
end{array}} right]$$
linear-algebra matrices inverse symmetric-matrices
linear-algebra matrices inverse symmetric-matrices
asked Nov 9 '18 at 10:47
AndreasAndreas
7,8281037
asked Nov 9 '18 at 10:47
AndreasAndreas
7,8281037
edited Nov 9 '18 at 15:16
Andreas
asked Nov 9 '18 at 10:47
AndreasAndreas
7,8281037
asked Nov 9 '18 at 10:47
AndreasAndreas
7,8281037
asked Nov 9 '18 at 10:47
AndreasAndreas
7,8281037
7,8281037
You might try the Cayley-Hamilton theorem. $A^{-1}$ can be written as a polynomial in $A$ and with some ingenuity you may be able to figure out the coefficients.
– Richard Martin
Nov 9 '18 at 11:00
Can you give us an example for $n$ being odd too?
– Mostafa Ayaz
Nov 9 '18 at 11:24
@MostafaAyaz The questions says $n$ even. For $n$ odd, as far as I see it, $det(A)=0$ so no inverse exists. You may want to prove this as well ....
– Andreas
Nov 9 '18 at 11:27
add a comment |
You might try the Cayley-Hamilton theorem. $A^{-1}$ can be written as a polynomial in $A$ and with some ingenuity you may be able to figure out the coefficients.
– Richard Martin
Nov 9 '18 at 11:00
Can you give us an example for $n$ being odd too?
– Mostafa Ayaz
Nov 9 '18 at 11:24
@MostafaAyaz The questions says $n$ even. For $n$ odd, as far as I see it, $det(A)=0$ so no inverse exists. You may want to prove this as well ....
– Andreas
Nov 9 '18 at 11:27
You might try the Cayley-Hamilton theorem. $A^{-1}$ can be written as a polynomial in $A$ and with some ingenuity you may be able to figure out the coefficients.
– Richard Martin
Nov 9 '18 at 11:00
You might try the Cayley-Hamilton theorem. $A^{-1}$ can be written as a polynomial in $A$ and with some ingenuity you may be able to figure out the coefficients.
– Richard Martin
Nov 9 '18 at 11:00
Can you give us an example for $n$ being odd too?
– Mostafa Ayaz
Nov 9 '18 at 11:24
Can you give us an example for $n$ being odd too?
– Mostafa Ayaz
Nov 9 '18 at 11:24
@MostafaAyaz The questions says $n$ even. For $n$ odd, as far as I see it, $det(A)=0$ so no inverse exists. You may want to prove this as well ....
– Andreas
Nov 9 '18 at 11:27
@MostafaAyaz The questions says $n$ even. For $n$ odd, as far as I see it, $det(A)=0$ so no inverse exists. You may want to prove this as well ....
– Andreas
Nov 9 '18 at 11:27
add a comment |
3 Answers
3
active
oldest
votes
Firstly Matrix is Toeplitz. This means it represents multiplication by power series expansion. This means matrix inversions corresponds to multiplicative inversion
Therefore, consider $$x+x^{-1}=frac{x^2+1}x$$ Now it's multiplicative inverse:
$$(x+x^{-1})^{-1}=frac x{x^2+1}$$
Now you can expand with geometric series / Taylor expansion for $$frac 1{x^2+1}=frac 1{1-(-1cdot x^2)}$$
And substitute with
$$frac{1}{1-t}=1+t+t^2+cdots, t=-x^2$$
and then finish. You will notice the flipping sign pattern and that the odd exponents disappear when you substitute and do the expansion.
answered Nov 9 '18 at 15:23
mathreadlermathreadler
14.8k72160
Good point! How does this explain the negative exponents? I.e . $frac x{x^2+1} = x^{-1}frac 1{1+ x^{-2}} = sum_{k=0}^infty (-1)^k x^{(-2 k-1)}$ would be the expansion for $|x|>1$ but can you simply augment these coefficients to the inverse Toeplitz matrix? And another question: how does this power series expansion explain that for odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 10 '18 at 14:17
@Andreas I tried making the explanation better.
– mathreadler
Nov 10 '18 at 17:33
Thanks for extending you text. However (please have a look at the question text and the example again) your expansion only gives the correct matrix entries for $i>j$. For $i<j$ one could generate entries by the symmetry condition $A_{i j}^{-1} = A_{j i}^{-1}$ or by the expansion I gave in my previous comment. However, I wonder if this "augmenting" is the only way to handle it, or if there is a more principled way. And another question remains: how does this power series expansion explain that for an $n times n$-Matrix $A$ with odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 11 '18 at 12:58
add a comment |
The most direct way to establish the conjecture is to perform the multiplication $E = A^{-1} A$ with the conjectured $A^{-1}$ and show that the result is the unit matrix. Since $A$ is bi-diagonal, each entry of $E$ is the sum of at most two terms, so there is little confusion.
$$E_{ik} = sum_{j=1}^n A^{-1}_{ij} A_{j k} = A^{-1}_{ij} A_{j, j-1} delta_{j-1,k} + A^{-1}_{ij} A_{j, j+1} delta_{j+1,k}\
= A^{-1}_{i, k+1} A_{k+1, k} + A^{-1}_{i, k-1} A_{k-1, k} \
= A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $$
Now the diagonal is
$$E_{ii}
= A^{-1}_{i, i+1} + A^{-1}_{i, i-1} $$
From the structure of $A^{-1}$, if $i$ is odd, then $A^{-1}_{i, i+1} = 1 $ and $ A^{-1}_{i, i-1} = 0 $. If $i$ is even, then $A^{-1}_{i, i+1} = 0 $ and $ A^{-1}_{i, i-1} = 1 $. So in all cases, $E_{ii} = 1$.
For $k ne i $, i.e the off-diagonal terms, we have $E_{ik} = A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $. From the structure of $A^{-1}$, either both of these summands are zero, or one is $+1$ and the other $-1$, as we have values of $(-1)^m$ for an index difference of $2m$. Hence, always $E_{ik} =0$.
This completes the proof. $qquad Box$
answered Nov 21 '18 at 17:23
AndreasAndreas
7,8281037
add a comment |
I found an algorithm that I hope it help you. Let the inverse be$$A^{-1}=begin{bmatrix}c_1&c_2&cdots&c_nend{bmatrix}$$In other words, $c_i$s are the columns of $A^{-1}$. We build the $c_i$s recursively as following:
$$c_{2}=e_1\c_{2k+2}=-c_{2k}+e_{2k+1}qquad,qquad 1le kle {nover 2}-1$$also $$c_{n-1}=e_n\c_{2k-1}=e_{2k}-c_{2k+1}qquad,qquad 1le kle {nover 2}-1$$where $e_i$s are the columns of $I_n$
answered Nov 9 '18 at 11:36
Mostafa AyazMostafa Ayaz
14.1k3937
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%2f2991218%2finverse-of-tridiagonal-toeplitz-matrix%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
Firstly Matrix is Toeplitz. This means it represents multiplication by power series expansion. This means matrix inversions corresponds to multiplicative inversion
Therefore, consider $$x+x^{-1}=frac{x^2+1}x$$ Now it's multiplicative inverse:
$$(x+x^{-1})^{-1}=frac x{x^2+1}$$
Now you can expand with geometric series / Taylor expansion for $$frac 1{x^2+1}=frac 1{1-(-1cdot x^2)}$$
And substitute with
$$frac{1}{1-t}=1+t+t^2+cdots, t=-x^2$$
and then finish. You will notice the flipping sign pattern and that the odd exponents disappear when you substitute and do the expansion.
answered Nov 9 '18 at 15:23
mathreadlermathreadler
14.8k72160
Good point! How does this explain the negative exponents? I.e . $frac x{x^2+1} = x^{-1}frac 1{1+ x^{-2}} = sum_{k=0}^infty (-1)^k x^{(-2 k-1)}$ would be the expansion for $|x|>1$ but can you simply augment these coefficients to the inverse Toeplitz matrix? And another question: how does this power series expansion explain that for odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 10 '18 at 14:17
@Andreas I tried making the explanation better.
– mathreadler
Nov 10 '18 at 17:33
Thanks for extending you text. However (please have a look at the question text and the example again) your expansion only gives the correct matrix entries for $i>j$. For $i<j$ one could generate entries by the symmetry condition $A_{i j}^{-1} = A_{j i}^{-1}$ or by the expansion I gave in my previous comment. However, I wonder if this "augmenting" is the only way to handle it, or if there is a more principled way. And another question remains: how does this power series expansion explain that for an $n times n$-Matrix $A$ with odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 11 '18 at 12:58
add a comment |
Firstly Matrix is Toeplitz. This means it represents multiplication by power series expansion. This means matrix inversions corresponds to multiplicative inversion
Therefore, consider $$x+x^{-1}=frac{x^2+1}x$$ Now it's multiplicative inverse:
$$(x+x^{-1})^{-1}=frac x{x^2+1}$$
Now you can expand with geometric series / Taylor expansion for $$frac 1{x^2+1}=frac 1{1-(-1cdot x^2)}$$
And substitute with
$$frac{1}{1-t}=1+t+t^2+cdots, t=-x^2$$
and then finish. You will notice the flipping sign pattern and that the odd exponents disappear when you substitute and do the expansion.
answered Nov 9 '18 at 15:23
mathreadlermathreadler
14.8k72160
Good point! How does this explain the negative exponents? I.e . $frac x{x^2+1} = x^{-1}frac 1{1+ x^{-2}} = sum_{k=0}^infty (-1)^k x^{(-2 k-1)}$ would be the expansion for $|x|>1$ but can you simply augment these coefficients to the inverse Toeplitz matrix? And another question: how does this power series expansion explain that for odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 10 '18 at 14:17
@Andreas I tried making the explanation better.
– mathreadler
Nov 10 '18 at 17:33
Thanks for extending you text. However (please have a look at the question text and the example again) your expansion only gives the correct matrix entries for $i>j$. For $i<j$ one could generate entries by the symmetry condition $A_{i j}^{-1} = A_{j i}^{-1}$ or by the expansion I gave in my previous comment. However, I wonder if this "augmenting" is the only way to handle it, or if there is a more principled way. And another question remains: how does this power series expansion explain that for an $n times n$-Matrix $A$ with odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 11 '18 at 12:58
add a comment |
Firstly Matrix is Toeplitz. This means it represents multiplication by power series expansion. This means matrix inversions corresponds to multiplicative inversion
Therefore, consider $$x+x^{-1}=frac{x^2+1}x$$ Now it's multiplicative inverse:
$$(x+x^{-1})^{-1}=frac x{x^2+1}$$
Now you can expand with geometric series / Taylor expansion for $$frac 1{x^2+1}=frac 1{1-(-1cdot x^2)}$$
And substitute with
$$frac{1}{1-t}=1+t+t^2+cdots, t=-x^2$$
and then finish. You will notice the flipping sign pattern and that the odd exponents disappear when you substitute and do the expansion.
answered Nov 9 '18 at 15:23
mathreadlermathreadler
14.8k72160
Firstly Matrix is Toeplitz. This means it represents multiplication by power series expansion. This means matrix inversions corresponds to multiplicative inversion
Therefore, consider $$x+x^{-1}=frac{x^2+1}x$$ Now it's multiplicative inverse:
$$(x+x^{-1})^{-1}=frac x{x^2+1}$$
Now you can expand with geometric series / Taylor expansion for $$frac 1{x^2+1}=frac 1{1-(-1cdot x^2)}$$
And substitute with
$$frac{1}{1-t}=1+t+t^2+cdots, t=-x^2$$
and then finish. You will notice the flipping sign pattern and that the odd exponents disappear when you substitute and do the expansion.
answered Nov 9 '18 at 15:23
mathreadlermathreadler
14.8k72160
edited Nov 10 '18 at 17:32
answered Nov 9 '18 at 15:23
mathreadlermathreadler
14.8k72160
answered Nov 9 '18 at 15:23
mathreadlermathreadler
14.8k72160
answered Nov 9 '18 at 15:23
mathreadlermathreadler
14.8k72160
14.8k72160
Good point! How does this explain the negative exponents? I.e . $frac x{x^2+1} = x^{-1}frac 1{1+ x^{-2}} = sum_{k=0}^infty (-1)^k x^{(-2 k-1)}$ would be the expansion for $|x|>1$ but can you simply augment these coefficients to the inverse Toeplitz matrix? And another question: how does this power series expansion explain that for odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 10 '18 at 14:17
@Andreas I tried making the explanation better.
– mathreadler
Nov 10 '18 at 17:33
Thanks for extending you text. However (please have a look at the question text and the example again) your expansion only gives the correct matrix entries for $i>j$. For $i<j$ one could generate entries by the symmetry condition $A_{i j}^{-1} = A_{j i}^{-1}$ or by the expansion I gave in my previous comment. However, I wonder if this "augmenting" is the only way to handle it, or if there is a more principled way. And another question remains: how does this power series expansion explain that for an $n times n$-Matrix $A$ with odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 11 '18 at 12:58
add a comment |
Good point! How does this explain the negative exponents? I.e . $frac x{x^2+1} = x^{-1}frac 1{1+ x^{-2}} = sum_{k=0}^infty (-1)^k x^{(-2 k-1)}$ would be the expansion for $|x|>1$ but can you simply augment these coefficients to the inverse Toeplitz matrix? And another question: how does this power series expansion explain that for odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 10 '18 at 14:17
@Andreas I tried making the explanation better.
– mathreadler
Nov 10 '18 at 17:33
Thanks for extending you text. However (please have a look at the question text and the example again) your expansion only gives the correct matrix entries for $i>j$. For $i<j$ one could generate entries by the symmetry condition $A_{i j}^{-1} = A_{j i}^{-1}$ or by the expansion I gave in my previous comment. However, I wonder if this "augmenting" is the only way to handle it, or if there is a more principled way. And another question remains: how does this power series expansion explain that for an $n times n$-Matrix $A$ with odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 11 '18 at 12:58
Good point! How does this explain the negative exponents? I.e . $frac x{x^2+1} = x^{-1}frac 1{1+ x^{-2}} = sum_{k=0}^infty (-1)^k x^{(-2 k-1)}$ would be the expansion for $|x|>1$ but can you simply augment these coefficients to the inverse Toeplitz matrix? And another question: how does this power series expansion explain that for odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 10 '18 at 14:17
Good point! How does this explain the negative exponents? I.e . $frac x{x^2+1} = x^{-1}frac 1{1+ x^{-2}} = sum_{k=0}^infty (-1)^k x^{(-2 k-1)}$ would be the expansion for $|x|>1$ but can you simply augment these coefficients to the inverse Toeplitz matrix? And another question: how does this power series expansion explain that for odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 10 '18 at 14:17
@Andreas I tried making the explanation better.
– mathreadler
Nov 10 '18 at 17:33
@Andreas I tried making the explanation better.
– mathreadler
Nov 10 '18 at 17:33
Thanks for extending you text. However (please have a look at the question text and the example again) your expansion only gives the correct matrix entries for $i>j$. For $i<j$ one could generate entries by the symmetry condition $A_{i j}^{-1} = A_{j i}^{-1}$ or by the expansion I gave in my previous comment. However, I wonder if this "augmenting" is the only way to handle it, or if there is a more principled way. And another question remains: how does this power series expansion explain that for an $n times n$-Matrix $A$ with odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 11 '18 at 12:58
Thanks for extending you text. However (please have a look at the question text and the example again) your expansion only gives the correct matrix entries for $i>j$. For $i<j$ one could generate entries by the symmetry condition $A_{i j}^{-1} = A_{j i}^{-1}$ or by the expansion I gave in my previous comment. However, I wonder if this "augmenting" is the only way to handle it, or if there is a more principled way. And another question remains: how does this power series expansion explain that for an $n times n$-Matrix $A$ with odd $n$, no inverse exists? Thanks for your help!
– Andreas
Nov 11 '18 at 12:58
add a comment |
The most direct way to establish the conjecture is to perform the multiplication $E = A^{-1} A$ with the conjectured $A^{-1}$ and show that the result is the unit matrix. Since $A$ is bi-diagonal, each entry of $E$ is the sum of at most two terms, so there is little confusion.
$$E_{ik} = sum_{j=1}^n A^{-1}_{ij} A_{j k} = A^{-1}_{ij} A_{j, j-1} delta_{j-1,k} + A^{-1}_{ij} A_{j, j+1} delta_{j+1,k}\
= A^{-1}_{i, k+1} A_{k+1, k} + A^{-1}_{i, k-1} A_{k-1, k} \
= A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $$
Now the diagonal is
$$E_{ii}
= A^{-1}_{i, i+1} + A^{-1}_{i, i-1} $$
From the structure of $A^{-1}$, if $i$ is odd, then $A^{-1}_{i, i+1} = 1 $ and $ A^{-1}_{i, i-1} = 0 $. If $i$ is even, then $A^{-1}_{i, i+1} = 0 $ and $ A^{-1}_{i, i-1} = 1 $. So in all cases, $E_{ii} = 1$.
For $k ne i $, i.e the off-diagonal terms, we have $E_{ik} = A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $. From the structure of $A^{-1}$, either both of these summands are zero, or one is $+1$ and the other $-1$, as we have values of $(-1)^m$ for an index difference of $2m$. Hence, always $E_{ik} =0$.
This completes the proof. $qquad Box$
answered Nov 21 '18 at 17:23
AndreasAndreas
7,8281037
add a comment |
The most direct way to establish the conjecture is to perform the multiplication $E = A^{-1} A$ with the conjectured $A^{-1}$ and show that the result is the unit matrix. Since $A$ is bi-diagonal, each entry of $E$ is the sum of at most two terms, so there is little confusion.
$$E_{ik} = sum_{j=1}^n A^{-1}_{ij} A_{j k} = A^{-1}_{ij} A_{j, j-1} delta_{j-1,k} + A^{-1}_{ij} A_{j, j+1} delta_{j+1,k}\
= A^{-1}_{i, k+1} A_{k+1, k} + A^{-1}_{i, k-1} A_{k-1, k} \
= A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $$
Now the diagonal is
$$E_{ii}
= A^{-1}_{i, i+1} + A^{-1}_{i, i-1} $$
From the structure of $A^{-1}$, if $i$ is odd, then $A^{-1}_{i, i+1} = 1 $ and $ A^{-1}_{i, i-1} = 0 $. If $i$ is even, then $A^{-1}_{i, i+1} = 0 $ and $ A^{-1}_{i, i-1} = 1 $. So in all cases, $E_{ii} = 1$.
For $k ne i $, i.e the off-diagonal terms, we have $E_{ik} = A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $. From the structure of $A^{-1}$, either both of these summands are zero, or one is $+1$ and the other $-1$, as we have values of $(-1)^m$ for an index difference of $2m$. Hence, always $E_{ik} =0$.
This completes the proof. $qquad Box$
answered Nov 21 '18 at 17:23
AndreasAndreas
7,8281037
add a comment |
The most direct way to establish the conjecture is to perform the multiplication $E = A^{-1} A$ with the conjectured $A^{-1}$ and show that the result is the unit matrix. Since $A$ is bi-diagonal, each entry of $E$ is the sum of at most two terms, so there is little confusion.
$$E_{ik} = sum_{j=1}^n A^{-1}_{ij} A_{j k} = A^{-1}_{ij} A_{j, j-1} delta_{j-1,k} + A^{-1}_{ij} A_{j, j+1} delta_{j+1,k}\
= A^{-1}_{i, k+1} A_{k+1, k} + A^{-1}_{i, k-1} A_{k-1, k} \
= A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $$
Now the diagonal is
$$E_{ii}
= A^{-1}_{i, i+1} + A^{-1}_{i, i-1} $$
From the structure of $A^{-1}$, if $i$ is odd, then $A^{-1}_{i, i+1} = 1 $ and $ A^{-1}_{i, i-1} = 0 $. If $i$ is even, then $A^{-1}_{i, i+1} = 0 $ and $ A^{-1}_{i, i-1} = 1 $. So in all cases, $E_{ii} = 1$.
For $k ne i $, i.e the off-diagonal terms, we have $E_{ik} = A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $. From the structure of $A^{-1}$, either both of these summands are zero, or one is $+1$ and the other $-1$, as we have values of $(-1)^m$ for an index difference of $2m$. Hence, always $E_{ik} =0$.
This completes the proof. $qquad Box$
answered Nov 21 '18 at 17:23
AndreasAndreas
7,8281037
The most direct way to establish the conjecture is to perform the multiplication $E = A^{-1} A$ with the conjectured $A^{-1}$ and show that the result is the unit matrix. Since $A$ is bi-diagonal, each entry of $E$ is the sum of at most two terms, so there is little confusion.
$$E_{ik} = sum_{j=1}^n A^{-1}_{ij} A_{j k} = A^{-1}_{ij} A_{j, j-1} delta_{j-1,k} + A^{-1}_{ij} A_{j, j+1} delta_{j+1,k}\
= A^{-1}_{i, k+1} A_{k+1, k} + A^{-1}_{i, k-1} A_{k-1, k} \
= A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $$
Now the diagonal is
$$E_{ii}
= A^{-1}_{i, i+1} + A^{-1}_{i, i-1} $$
From the structure of $A^{-1}$, if $i$ is odd, then $A^{-1}_{i, i+1} = 1 $ and $ A^{-1}_{i, i-1} = 0 $. If $i$ is even, then $A^{-1}_{i, i+1} = 0 $ and $ A^{-1}_{i, i-1} = 1 $. So in all cases, $E_{ii} = 1$.
For $k ne i $, i.e the off-diagonal terms, we have $E_{ik} = A^{-1}_{i, k+1} + A^{-1}_{i, k-1} $. From the structure of $A^{-1}$, either both of these summands are zero, or one is $+1$ and the other $-1$, as we have values of $(-1)^m$ for an index difference of $2m$. Hence, always $E_{ik} =0$.
This completes the proof. $qquad Box$
answered Nov 21 '18 at 17:23
AndreasAndreas
7,8281037
answered Nov 21 '18 at 17:23
AndreasAndreas
7,8281037
answered Nov 21 '18 at 17:23
AndreasAndreas
7,8281037
answered Nov 21 '18 at 17:23
AndreasAndreas
7,8281037
7,8281037
add a comment |
add a comment |
I found an algorithm that I hope it help you. Let the inverse be$$A^{-1}=begin{bmatrix}c_1&c_2&cdots&c_nend{bmatrix}$$In other words, $c_i$s are the columns of $A^{-1}$. We build the $c_i$s recursively as following:
$$c_{2}=e_1\c_{2k+2}=-c_{2k}+e_{2k+1}qquad,qquad 1le kle {nover 2}-1$$also $$c_{n-1}=e_n\c_{2k-1}=e_{2k}-c_{2k+1}qquad,qquad 1le kle {nover 2}-1$$where $e_i$s are the columns of $I_n$
answered Nov 9 '18 at 11:36
Mostafa AyazMostafa Ayaz
14.1k3937
add a comment |
I found an algorithm that I hope it help you. Let the inverse be$$A^{-1}=begin{bmatrix}c_1&c_2&cdots&c_nend{bmatrix}$$In other words, $c_i$s are the columns of $A^{-1}$. We build the $c_i$s recursively as following:
$$c_{2}=e_1\c_{2k+2}=-c_{2k}+e_{2k+1}qquad,qquad 1le kle {nover 2}-1$$also $$c_{n-1}=e_n\c_{2k-1}=e_{2k}-c_{2k+1}qquad,qquad 1le kle {nover 2}-1$$where $e_i$s are the columns of $I_n$
answered Nov 9 '18 at 11:36
Mostafa AyazMostafa Ayaz
14.1k3937
add a comment |
I found an algorithm that I hope it help you. Let the inverse be$$A^{-1}=begin{bmatrix}c_1&c_2&cdots&c_nend{bmatrix}$$In other words, $c_i$s are the columns of $A^{-1}$. We build the $c_i$s recursively as following:
$$c_{2}=e_1\c_{2k+2}=-c_{2k}+e_{2k+1}qquad,qquad 1le kle {nover 2}-1$$also $$c_{n-1}=e_n\c_{2k-1}=e_{2k}-c_{2k+1}qquad,qquad 1le kle {nover 2}-1$$where $e_i$s are the columns of $I_n$
answered Nov 9 '18 at 11:36
Mostafa AyazMostafa Ayaz
14.1k3937
I found an algorithm that I hope it help you. Let the inverse be$$A^{-1}=begin{bmatrix}c_1&c_2&cdots&c_nend{bmatrix}$$In other words, $c_i$s are the columns of $A^{-1}$. We build the $c_i$s recursively as following:
$$c_{2}=e_1\c_{2k+2}=-c_{2k}+e_{2k+1}qquad,qquad 1le kle {nover 2}-1$$also $$c_{n-1}=e_n\c_{2k-1}=e_{2k}-c_{2k+1}qquad,qquad 1le kle {nover 2}-1$$where $e_i$s are the columns of $I_n$
answered Nov 9 '18 at 11:36
Mostafa AyazMostafa Ayaz
14.1k3937
answered Nov 9 '18 at 11:36
Mostafa AyazMostafa Ayaz
14.1k3937
answered Nov 9 '18 at 11:36
Mostafa AyazMostafa Ayaz
14.1k3937
answered Nov 9 '18 at 11:36
Mostafa AyazMostafa Ayaz
14.1k3937
14.1k3937
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.
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%2f2991218%2finverse-of-tridiagonal-toeplitz-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
You might try the Cayley-Hamilton theorem. $A^{-1}$ can be written as a polynomial in $A$ and with some ingenuity you may be able to figure out the coefficients.
– Richard Martin
Nov 9 '18 at 11:00
Can you give us an example for $n$ being odd too?
– Mostafa Ayaz
Nov 9 '18 at 11:24
@MostafaAyaz The questions says $n$ even. For $n$ odd, as far as I see it, $det(A)=0$ so no inverse exists. You may want to prove this as well ....
– Andreas
Nov 9 '18 at 11:27