Determinants of tridiagonal matrices
$begingroup$
A square matrix $A = [a_{ij}]$ is called ${bf tridiagonal}$ if
$a_{ij}=0$ for $|i-j|>1$. Try to guess a formula for the determinant
of tridiagonal matrix, say $a_i = a_{ii}$ for $i=1,...,n$, $b_i =
a_{i,i+1}$ and $c_i = a_{i+1,i}$ for $i=1,...,n-1$.
Attempt
So, I was thinking on reducing to smaller matrix. Say for $n=1$, we det A = $a_1$. Not in the case $n=2$, we have just the matrix with rows $[a_1, b_1$] and $[c_1,a_2]$. Thus,
$$ det A = a_1 a_2 - c_1 b_1 $$
Now, for the $n=3$ case, we start to see the zeros appear, but it becomes cumbersome to compute determinant after $n>3$. Is there a way to find closed nice for this problem? Or do I have to keep doing it expressing the actual determinant in terms of the previous as it is evident in the case $n=3$ since if we call $D_n$ to be the determinant on the nth case (for instnace, we saw that $D_2 = a_1 a_2 - c_1 b_1$ so that for the $n=3$ case I see that
$$ D_3 =a_3 D_2 - c_2 b_2 a_1 $$
Is this the right way to approach this problem? Moreover, why are tridiagonal matrices so important? Can someone give intuition into what they do? or in what situations we use them
linear-algebra
asked Dec 21 '18 at 9:09
Jimmy SabaterJimmy Sabater
2,645323
$endgroup$
add a comment |
$begingroup$
A square matrix $A = [a_{ij}]$ is called ${bf tridiagonal}$ if
$a_{ij}=0$ for $|i-j|>1$. Try to guess a formula for the determinant
of tridiagonal matrix, say $a_i = a_{ii}$ for $i=1,...,n$, $b_i =
a_{i,i+1}$ and $c_i = a_{i+1,i}$ for $i=1,...,n-1$.
Attempt
So, I was thinking on reducing to smaller matrix. Say for $n=1$, we det A = $a_1$. Not in the case $n=2$, we have just the matrix with rows $[a_1, b_1$] and $[c_1,a_2]$. Thus,
$$ det A = a_1 a_2 - c_1 b_1 $$
Now, for the $n=3$ case, we start to see the zeros appear, but it becomes cumbersome to compute determinant after $n>3$. Is there a way to find closed nice for this problem? Or do I have to keep doing it expressing the actual determinant in terms of the previous as it is evident in the case $n=3$ since if we call $D_n$ to be the determinant on the nth case (for instnace, we saw that $D_2 = a_1 a_2 - c_1 b_1$ so that for the $n=3$ case I see that
$$ D_3 =a_3 D_2 - c_2 b_2 a_1 $$
Is this the right way to approach this problem? Moreover, why are tridiagonal matrices so important? Can someone give intuition into what they do? or in what situations we use them
linear-algebra
asked Dec 21 '18 at 9:09
Jimmy SabaterJimmy Sabater
2,645323
$endgroup$
$begingroup$
Related
$endgroup$
– A.Γ.
Dec 21 '18 at 9:36
add a comment |
$begingroup$
A square matrix $A = [a_{ij}]$ is called ${bf tridiagonal}$ if
$a_{ij}=0$ for $|i-j|>1$. Try to guess a formula for the determinant
of tridiagonal matrix, say $a_i = a_{ii}$ for $i=1,...,n$, $b_i =
a_{i,i+1}$ and $c_i = a_{i+1,i}$ for $i=1,...,n-1$.
Attempt
So, I was thinking on reducing to smaller matrix. Say for $n=1$, we det A = $a_1$. Not in the case $n=2$, we have just the matrix with rows $[a_1, b_1$] and $[c_1,a_2]$. Thus,
$$ det A = a_1 a_2 - c_1 b_1 $$
Now, for the $n=3$ case, we start to see the zeros appear, but it becomes cumbersome to compute determinant after $n>3$. Is there a way to find closed nice for this problem? Or do I have to keep doing it expressing the actual determinant in terms of the previous as it is evident in the case $n=3$ since if we call $D_n$ to be the determinant on the nth case (for instnace, we saw that $D_2 = a_1 a_2 - c_1 b_1$ so that for the $n=3$ case I see that
$$ D_3 =a_3 D_2 - c_2 b_2 a_1 $$
Is this the right way to approach this problem? Moreover, why are tridiagonal matrices so important? Can someone give intuition into what they do? or in what situations we use them
linear-algebra
asked Dec 21 '18 at 9:09
Jimmy SabaterJimmy Sabater
2,645323
$endgroup$
A square matrix $A = [a_{ij}]$ is called ${bf tridiagonal}$ if
$a_{ij}=0$ for $|i-j|>1$. Try to guess a formula for the determinant
of tridiagonal matrix, say $a_i = a_{ii}$ for $i=1,...,n$, $b_i =
a_{i,i+1}$ and $c_i = a_{i+1,i}$ for $i=1,...,n-1$.
Attempt
So, I was thinking on reducing to smaller matrix. Say for $n=1$, we det A = $a_1$. Not in the case $n=2$, we have just the matrix with rows $[a_1, b_1$] and $[c_1,a_2]$. Thus,
$$ det A = a_1 a_2 - c_1 b_1 $$
Now, for the $n=3$ case, we start to see the zeros appear, but it becomes cumbersome to compute determinant after $n>3$. Is there a way to find closed nice for this problem? Or do I have to keep doing it expressing the actual determinant in terms of the previous as it is evident in the case $n=3$ since if we call $D_n$ to be the determinant on the nth case (for instnace, we saw that $D_2 = a_1 a_2 - c_1 b_1$ so that for the $n=3$ case I see that
$$ D_3 =a_3 D_2 - c_2 b_2 a_1 $$
Is this the right way to approach this problem? Moreover, why are tridiagonal matrices so important? Can someone give intuition into what they do? or in what situations we use them
linear-algebra
linear-algebra
asked Dec 21 '18 at 9:09
Jimmy SabaterJimmy Sabater
2,645323
asked Dec 21 '18 at 9:09
Jimmy SabaterJimmy Sabater
2,645323
asked Dec 21 '18 at 9:09
Jimmy SabaterJimmy Sabater
2,645323
asked Dec 21 '18 at 9:09
Jimmy SabaterJimmy Sabater
2,645323
asked Dec 21 '18 at 9:09
Jimmy SabaterJimmy Sabater
2,645323
2,645323
$begingroup$
Related
$endgroup$
– A.Γ.
Dec 21 '18 at 9:36
add a comment |
$begingroup$
Related
$endgroup$
– A.Γ.
Dec 21 '18 at 9:36
$begingroup$
Related
$endgroup$
– A.Γ.
Dec 21 '18 at 9:36
$begingroup$
Related
$endgroup$
– A.Γ.
Dec 21 '18 at 9:36
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Recursion is the best way to solve this problem. As a hint, you showed that $$D_3 = a_3D_2-c_2b_2a_1 = a_3D_2 - c_2b_2D_1.$$ Can you generalize this to a formula for $D_n$ in terms of $D_{n-1}$, $D_{n-2}$, and a few of the entries of the matrix?
As for why they are important, many eigenvalue algorithms for symmetric/Hermitian matrices will first use similarity transforms to reduce the matrix to a tridiagonal form, and then find the eigenvalues of a tridiagonal matrix.
Also, tridiagonal matrices come up when solving differential equations via discretization. Suppose we want to solve the $u''(x) = f(x)$ on the interval $[0,1]$. Pick a positive integer $N$, and let $v_n = u(tfrac{n}{N})$ for $n = 0,1,ldots,N$. Then, using an approximation of the second derivative, we have $$f(tfrac{n}{N}) = u''(tfrac{n}{N}) approx dfrac{u(tfrac{n+1}{N})-2u(tfrac{n}{N})+u(tfrac{n-1}{N})}{(tfrac{1}{N})^2} = N^2(v_{n+1}-2v_n+v_{n-1}).$$ If we do this for all $n = 1, 2, ldots, N-1$, and then include equations for whatever boundary conditions we might have, we'll get a tridiagonal system of equations. Note, this was a fairly trivial example, but there are more complicated differential equations and PDEs that can be handled this way.
answered Dec 21 '18 at 9:21
JimmyK4542JimmyK4542
41.1k245106
$endgroup$
$begingroup$
Thanks so much for the explanation. Its very nice. Just one question, how is $v_n = u (n/N)$ in $mathbb{R}^{N+1}$? arent the $v_n$ just terms of a sequence?
$endgroup$
– Jimmy Sabater
Dec 21 '18 at 22:21
$begingroup$
I was intending for $v$ to be a vector whose $n$-th entry is $v_n = u(n/N)$, and then write the system of equations in matrix form. I think I realized afterwards that writing the full system of equations wasn't really necessary for this answer. Sorry for the notational confusion.
$endgroup$
– JimmyK4542
Dec 21 '18 at 22:47
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%2f3048319%2fdeterminants-of-tridiagonal-matrices%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$
Recursion is the best way to solve this problem. As a hint, you showed that $$D_3 = a_3D_2-c_2b_2a_1 = a_3D_2 - c_2b_2D_1.$$ Can you generalize this to a formula for $D_n$ in terms of $D_{n-1}$, $D_{n-2}$, and a few of the entries of the matrix?
As for why they are important, many eigenvalue algorithms for symmetric/Hermitian matrices will first use similarity transforms to reduce the matrix to a tridiagonal form, and then find the eigenvalues of a tridiagonal matrix.
Also, tridiagonal matrices come up when solving differential equations via discretization. Suppose we want to solve the $u''(x) = f(x)$ on the interval $[0,1]$. Pick a positive integer $N$, and let $v_n = u(tfrac{n}{N})$ for $n = 0,1,ldots,N$. Then, using an approximation of the second derivative, we have $$f(tfrac{n}{N}) = u''(tfrac{n}{N}) approx dfrac{u(tfrac{n+1}{N})-2u(tfrac{n}{N})+u(tfrac{n-1}{N})}{(tfrac{1}{N})^2} = N^2(v_{n+1}-2v_n+v_{n-1}).$$ If we do this for all $n = 1, 2, ldots, N-1$, and then include equations for whatever boundary conditions we might have, we'll get a tridiagonal system of equations. Note, this was a fairly trivial example, but there are more complicated differential equations and PDEs that can be handled this way.
answered Dec 21 '18 at 9:21
JimmyK4542JimmyK4542
41.1k245106
$endgroup$
$begingroup$
Thanks so much for the explanation. Its very nice. Just one question, how is $v_n = u (n/N)$ in $mathbb{R}^{N+1}$? arent the $v_n$ just terms of a sequence?
$endgroup$
– Jimmy Sabater
Dec 21 '18 at 22:21
$begingroup$
I was intending for $v$ to be a vector whose $n$-th entry is $v_n = u(n/N)$, and then write the system of equations in matrix form. I think I realized afterwards that writing the full system of equations wasn't really necessary for this answer. Sorry for the notational confusion.
$endgroup$
– JimmyK4542
Dec 21 '18 at 22:47
add a comment |
$begingroup$
Recursion is the best way to solve this problem. As a hint, you showed that $$D_3 = a_3D_2-c_2b_2a_1 = a_3D_2 - c_2b_2D_1.$$ Can you generalize this to a formula for $D_n$ in terms of $D_{n-1}$, $D_{n-2}$, and a few of the entries of the matrix?
As for why they are important, many eigenvalue algorithms for symmetric/Hermitian matrices will first use similarity transforms to reduce the matrix to a tridiagonal form, and then find the eigenvalues of a tridiagonal matrix.
Also, tridiagonal matrices come up when solving differential equations via discretization. Suppose we want to solve the $u''(x) = f(x)$ on the interval $[0,1]$. Pick a positive integer $N$, and let $v_n = u(tfrac{n}{N})$ for $n = 0,1,ldots,N$. Then, using an approximation of the second derivative, we have $$f(tfrac{n}{N}) = u''(tfrac{n}{N}) approx dfrac{u(tfrac{n+1}{N})-2u(tfrac{n}{N})+u(tfrac{n-1}{N})}{(tfrac{1}{N})^2} = N^2(v_{n+1}-2v_n+v_{n-1}).$$ If we do this for all $n = 1, 2, ldots, N-1$, and then include equations for whatever boundary conditions we might have, we'll get a tridiagonal system of equations. Note, this was a fairly trivial example, but there are more complicated differential equations and PDEs that can be handled this way.
answered Dec 21 '18 at 9:21
JimmyK4542JimmyK4542
41.1k245106
$endgroup$
$begingroup$
Thanks so much for the explanation. Its very nice. Just one question, how is $v_n = u (n/N)$ in $mathbb{R}^{N+1}$? arent the $v_n$ just terms of a sequence?
$endgroup$
– Jimmy Sabater
Dec 21 '18 at 22:21
$begingroup$
I was intending for $v$ to be a vector whose $n$-th entry is $v_n = u(n/N)$, and then write the system of equations in matrix form. I think I realized afterwards that writing the full system of equations wasn't really necessary for this answer. Sorry for the notational confusion.
$endgroup$
– JimmyK4542
Dec 21 '18 at 22:47
add a comment |
$begingroup$
Recursion is the best way to solve this problem. As a hint, you showed that $$D_3 = a_3D_2-c_2b_2a_1 = a_3D_2 - c_2b_2D_1.$$ Can you generalize this to a formula for $D_n$ in terms of $D_{n-1}$, $D_{n-2}$, and a few of the entries of the matrix?
As for why they are important, many eigenvalue algorithms for symmetric/Hermitian matrices will first use similarity transforms to reduce the matrix to a tridiagonal form, and then find the eigenvalues of a tridiagonal matrix.
Also, tridiagonal matrices come up when solving differential equations via discretization. Suppose we want to solve the $u''(x) = f(x)$ on the interval $[0,1]$. Pick a positive integer $N$, and let $v_n = u(tfrac{n}{N})$ for $n = 0,1,ldots,N$. Then, using an approximation of the second derivative, we have $$f(tfrac{n}{N}) = u''(tfrac{n}{N}) approx dfrac{u(tfrac{n+1}{N})-2u(tfrac{n}{N})+u(tfrac{n-1}{N})}{(tfrac{1}{N})^2} = N^2(v_{n+1}-2v_n+v_{n-1}).$$ If we do this for all $n = 1, 2, ldots, N-1$, and then include equations for whatever boundary conditions we might have, we'll get a tridiagonal system of equations. Note, this was a fairly trivial example, but there are more complicated differential equations and PDEs that can be handled this way.
answered Dec 21 '18 at 9:21
JimmyK4542JimmyK4542
41.1k245106
$endgroup$
Recursion is the best way to solve this problem. As a hint, you showed that $$D_3 = a_3D_2-c_2b_2a_1 = a_3D_2 - c_2b_2D_1.$$ Can you generalize this to a formula for $D_n$ in terms of $D_{n-1}$, $D_{n-2}$, and a few of the entries of the matrix?
As for why they are important, many eigenvalue algorithms for symmetric/Hermitian matrices will first use similarity transforms to reduce the matrix to a tridiagonal form, and then find the eigenvalues of a tridiagonal matrix.
Also, tridiagonal matrices come up when solving differential equations via discretization. Suppose we want to solve the $u''(x) = f(x)$ on the interval $[0,1]$. Pick a positive integer $N$, and let $v_n = u(tfrac{n}{N})$ for $n = 0,1,ldots,N$. Then, using an approximation of the second derivative, we have $$f(tfrac{n}{N}) = u''(tfrac{n}{N}) approx dfrac{u(tfrac{n+1}{N})-2u(tfrac{n}{N})+u(tfrac{n-1}{N})}{(tfrac{1}{N})^2} = N^2(v_{n+1}-2v_n+v_{n-1}).$$ If we do this for all $n = 1, 2, ldots, N-1$, and then include equations for whatever boundary conditions we might have, we'll get a tridiagonal system of equations. Note, this was a fairly trivial example, but there are more complicated differential equations and PDEs that can be handled this way.
answered Dec 21 '18 at 9:21
JimmyK4542JimmyK4542
41.1k245106
edited Dec 21 '18 at 22:44
answered Dec 21 '18 at 9:21
JimmyK4542JimmyK4542
41.1k245106
answered Dec 21 '18 at 9:21
JimmyK4542JimmyK4542
41.1k245106
answered Dec 21 '18 at 9:21
JimmyK4542JimmyK4542
41.1k245106
41.1k245106
$begingroup$
Thanks so much for the explanation. Its very nice. Just one question, how is $v_n = u (n/N)$ in $mathbb{R}^{N+1}$? arent the $v_n$ just terms of a sequence?
$endgroup$
– Jimmy Sabater
Dec 21 '18 at 22:21
$begingroup$
I was intending for $v$ to be a vector whose $n$-th entry is $v_n = u(n/N)$, and then write the system of equations in matrix form. I think I realized afterwards that writing the full system of equations wasn't really necessary for this answer. Sorry for the notational confusion.
$endgroup$
– JimmyK4542
Dec 21 '18 at 22:47
add a comment |
$begingroup$
Thanks so much for the explanation. Its very nice. Just one question, how is $v_n = u (n/N)$ in $mathbb{R}^{N+1}$? arent the $v_n$ just terms of a sequence?
$endgroup$
– Jimmy Sabater
Dec 21 '18 at 22:21
$begingroup$
I was intending for $v$ to be a vector whose $n$-th entry is $v_n = u(n/N)$, and then write the system of equations in matrix form. I think I realized afterwards that writing the full system of equations wasn't really necessary for this answer. Sorry for the notational confusion.
$endgroup$
– JimmyK4542
Dec 21 '18 at 22:47
$begingroup$
Thanks so much for the explanation. Its very nice. Just one question, how is $v_n = u (n/N)$ in $mathbb{R}^{N+1}$? arent the $v_n$ just terms of a sequence?
$endgroup$
– Jimmy Sabater
Dec 21 '18 at 22:21
$begingroup$
Thanks so much for the explanation. Its very nice. Just one question, how is $v_n = u (n/N)$ in $mathbb{R}^{N+1}$? arent the $v_n$ just terms of a sequence?
$endgroup$
– Jimmy Sabater
Dec 21 '18 at 22:21
$begingroup$
I was intending for $v$ to be a vector whose $n$-th entry is $v_n = u(n/N)$, and then write the system of equations in matrix form. I think I realized afterwards that writing the full system of equations wasn't really necessary for this answer. Sorry for the notational confusion.
$endgroup$
– JimmyK4542
Dec 21 '18 at 22:47
$begingroup$
I was intending for $v$ to be a vector whose $n$-th entry is $v_n = u(n/N)$, and then write the system of equations in matrix form. I think I realized afterwards that writing the full system of equations wasn't really necessary for this answer. Sorry for the notational confusion.
$endgroup$
– JimmyK4542
Dec 21 '18 at 22:47
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%2f3048319%2fdeterminants-of-tridiagonal-matrices%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$
Related
$endgroup$
– A.Γ.
Dec 21 '18 at 9:36