Is the “term-matrix†of a $C$-finite sequence full rank?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
A linear recurrence relation with constant coefficients is sometimes called a $C$-finite sequence. That is, a sequence $a_n$ is $C$-finite iff $$a_n = sum_k = 1^d c_k a_n - k$$ for all suitable $n$, where $c_1, dots, c_d$ are some constants and $d$ is a positive integer. The degree of a $C$-finite sequence is the smallest such $d$ for which this holds.
If $a_n$ is a nonzero $C$-finite sequence with degree $d$, is the matrix
beginequation*
beginbmatrix
a_d - 1 & a_d - 2 & cdots & a_0 \
a_d & a_d - 1 & cdots & a_1 \
vdots & vdots & vdots & vdots \
a_2d - 2 & a_2d - 3 & cdots & a_d - 1
endbmatrix
endequation*
full-rank?
(Note that some obvious "counterexamples" are actually not. For example, take $a_n = a_n - 1 / 2 + a_n - 2 / 2$ with $a_0 = a_1 = 1$. This sequence reduces to a constant, which has degree 1, not 2.)
As a further question, if we construct a matrix of the same form, but of order $m neq d$, can we say anything about the rank of the matrix then?
I came across this question while trying to justify the following technique: Suppose that we have a sequence $a_n$ that we suspect of being a degree $d$ $C$-finite sequence. If this were the case, then the following system would be consistent:
beginalign
labeleqn:recurrence-guess
beginsplit
a_d - 1 c_1 + a_d - 2 c_2 + cdots + a_0 c_d &= a_d \
a_d c_1 + a_d - 1 c_2 + cdots + a_1 c_d &= a_d + 1 \
&vdots \
a_2d - 2 c_1 + a_2d - 3 c_2 + cdots + a_d - 1 c_d &= a_2d - 1.
endsplit
endalign
This is a square system of order $d$ with coefficient matrix
beginequation*
beginbmatrix
a_d - 1 & a_d - 2 & cdots & a_0 \
a_d & a_d - 1 & cdots & a_1 \
vdots & vdots & vdots & vdots \
a_2d - 2 & a_2d - 3 & cdots & a_d - 1
endbmatrix.
endequation*
Solving this for the coefficients gives us a nice conjecture.
It would be desirable that an actual $C$-finite sequence makes this coefficient matrix be full-rank, so that the coefficients are unique.
linear-algebra sequences-and-series recurrence-relations
asked Aug 27 at 18:41
rwbogl
819417
add a comment |Â
up vote
1
down vote
favorite
A linear recurrence relation with constant coefficients is sometimes called a $C$-finite sequence. That is, a sequence $a_n$ is $C$-finite iff $$a_n = sum_k = 1^d c_k a_n - k$$ for all suitable $n$, where $c_1, dots, c_d$ are some constants and $d$ is a positive integer. The degree of a $C$-finite sequence is the smallest such $d$ for which this holds.
If $a_n$ is a nonzero $C$-finite sequence with degree $d$, is the matrix
beginequation*
beginbmatrix
a_d - 1 & a_d - 2 & cdots & a_0 \
a_d & a_d - 1 & cdots & a_1 \
vdots & vdots & vdots & vdots \
a_2d - 2 & a_2d - 3 & cdots & a_d - 1
endbmatrix
endequation*
full-rank?
(Note that some obvious "counterexamples" are actually not. For example, take $a_n = a_n - 1 / 2 + a_n - 2 / 2$ with $a_0 = a_1 = 1$. This sequence reduces to a constant, which has degree 1, not 2.)
As a further question, if we construct a matrix of the same form, but of order $m neq d$, can we say anything about the rank of the matrix then?
I came across this question while trying to justify the following technique: Suppose that we have a sequence $a_n$ that we suspect of being a degree $d$ $C$-finite sequence. If this were the case, then the following system would be consistent:
beginalign
labeleqn:recurrence-guess
beginsplit
a_d - 1 c_1 + a_d - 2 c_2 + cdots + a_0 c_d &= a_d \
a_d c_1 + a_d - 1 c_2 + cdots + a_1 c_d &= a_d + 1 \
&vdots \
a_2d - 2 c_1 + a_2d - 3 c_2 + cdots + a_d - 1 c_d &= a_2d - 1.
endsplit
endalign
This is a square system of order $d$ with coefficient matrix
beginequation*
beginbmatrix
a_d - 1 & a_d - 2 & cdots & a_0 \
a_d & a_d - 1 & cdots & a_1 \
vdots & vdots & vdots & vdots \
a_2d - 2 & a_2d - 3 & cdots & a_d - 1
endbmatrix.
endequation*
Solving this for the coefficients gives us a nice conjecture.
It would be desirable that an actual $C$-finite sequence makes this coefficient matrix be full-rank, so that the coefficients are unique.
linear-algebra sequences-and-series recurrence-relations
asked Aug 27 at 18:41
rwbogl
819417
1
I think it is true, and the proof is roughly this; assuming it is not full rank, then the rows are linearly dependent. This linear dependence gives you a recurrence for $a_n$ with a smaller value of $d$, contradiction.
– Mike Earnest
Aug 27 at 19:46
@MikeEarnest That was my thought as well. I couldn't find a way to make this work, but perhaps I just need to go manipulate some more sums until it happens.
– rwbogl
Aug 27 at 20:10
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
A linear recurrence relation with constant coefficients is sometimes called a $C$-finite sequence. That is, a sequence $a_n$ is $C$-finite iff $$a_n = sum_k = 1^d c_k a_n - k$$ for all suitable $n$, where $c_1, dots, c_d$ are some constants and $d$ is a positive integer. The degree of a $C$-finite sequence is the smallest such $d$ for which this holds.
If $a_n$ is a nonzero $C$-finite sequence with degree $d$, is the matrix
beginequation*
beginbmatrix
a_d - 1 & a_d - 2 & cdots & a_0 \
a_d & a_d - 1 & cdots & a_1 \
vdots & vdots & vdots & vdots \
a_2d - 2 & a_2d - 3 & cdots & a_d - 1
endbmatrix
endequation*
full-rank?
(Note that some obvious "counterexamples" are actually not. For example, take $a_n = a_n - 1 / 2 + a_n - 2 / 2$ with $a_0 = a_1 = 1$. This sequence reduces to a constant, which has degree 1, not 2.)
As a further question, if we construct a matrix of the same form, but of order $m neq d$, can we say anything about the rank of the matrix then?
I came across this question while trying to justify the following technique: Suppose that we have a sequence $a_n$ that we suspect of being a degree $d$ $C$-finite sequence. If this were the case, then the following system would be consistent:
beginalign
labeleqn:recurrence-guess
beginsplit
a_d - 1 c_1 + a_d - 2 c_2 + cdots + a_0 c_d &= a_d \
a_d c_1 + a_d - 1 c_2 + cdots + a_1 c_d &= a_d + 1 \
&vdots \
a_2d - 2 c_1 + a_2d - 3 c_2 + cdots + a_d - 1 c_d &= a_2d - 1.
endsplit
endalign
This is a square system of order $d$ with coefficient matrix
beginequation*
beginbmatrix
a_d - 1 & a_d - 2 & cdots & a_0 \
a_d & a_d - 1 & cdots & a_1 \
vdots & vdots & vdots & vdots \
a_2d - 2 & a_2d - 3 & cdots & a_d - 1
endbmatrix.
endequation*
Solving this for the coefficients gives us a nice conjecture.
It would be desirable that an actual $C$-finite sequence makes this coefficient matrix be full-rank, so that the coefficients are unique.
linear-algebra sequences-and-series recurrence-relations
asked Aug 27 at 18:41
rwbogl
819417
A linear recurrence relation with constant coefficients is sometimes called a $C$-finite sequence. That is, a sequence $a_n$ is $C$-finite iff $$a_n = sum_k = 1^d c_k a_n - k$$ for all suitable $n$, where $c_1, dots, c_d$ are some constants and $d$ is a positive integer. The degree of a $C$-finite sequence is the smallest such $d$ for which this holds.
If $a_n$ is a nonzero $C$-finite sequence with degree $d$, is the matrix
beginequation*
beginbmatrix
a_d - 1 & a_d - 2 & cdots & a_0 \
a_d & a_d - 1 & cdots & a_1 \
vdots & vdots & vdots & vdots \
a_2d - 2 & a_2d - 3 & cdots & a_d - 1
endbmatrix
endequation*
full-rank?
(Note that some obvious "counterexamples" are actually not. For example, take $a_n = a_n - 1 / 2 + a_n - 2 / 2$ with $a_0 = a_1 = 1$. This sequence reduces to a constant, which has degree 1, not 2.)
As a further question, if we construct a matrix of the same form, but of order $m neq d$, can we say anything about the rank of the matrix then?
I came across this question while trying to justify the following technique: Suppose that we have a sequence $a_n$ that we suspect of being a degree $d$ $C$-finite sequence. If this were the case, then the following system would be consistent:
beginalign
labeleqn:recurrence-guess
beginsplit
a_d - 1 c_1 + a_d - 2 c_2 + cdots + a_0 c_d &= a_d \
a_d c_1 + a_d - 1 c_2 + cdots + a_1 c_d &= a_d + 1 \
&vdots \
a_2d - 2 c_1 + a_2d - 3 c_2 + cdots + a_d - 1 c_d &= a_2d - 1.
endsplit
endalign
This is a square system of order $d$ with coefficient matrix
beginequation*
beginbmatrix
a_d - 1 & a_d - 2 & cdots & a_0 \
a_d & a_d - 1 & cdots & a_1 \
vdots & vdots & vdots & vdots \
a_2d - 2 & a_2d - 3 & cdots & a_d - 1
endbmatrix.
endequation*
Solving this for the coefficients gives us a nice conjecture.
It would be desirable that an actual $C$-finite sequence makes this coefficient matrix be full-rank, so that the coefficients are unique.
linear-algebra sequences-and-series recurrence-relations
asked Aug 27 at 18:41
rwbogl
819417
asked Aug 27 at 18:41
rwbogl
819417
asked Aug 27 at 18:41
rwbogl
819417
asked Aug 27 at 18:41
rwbogl
819417
819417
1
I think it is true, and the proof is roughly this; assuming it is not full rank, then the rows are linearly dependent. This linear dependence gives you a recurrence for $a_n$ with a smaller value of $d$, contradiction.
– Mike Earnest
Aug 27 at 19:46
@MikeEarnest That was my thought as well. I couldn't find a way to make this work, but perhaps I just need to go manipulate some more sums until it happens.
– rwbogl
Aug 27 at 20:10
add a comment |Â
1
I think it is true, and the proof is roughly this; assuming it is not full rank, then the rows are linearly dependent. This linear dependence gives you a recurrence for $a_n$ with a smaller value of $d$, contradiction.
– Mike Earnest
Aug 27 at 19:46
@MikeEarnest That was my thought as well. I couldn't find a way to make this work, but perhaps I just need to go manipulate some more sums until it happens.
– rwbogl
Aug 27 at 20:10
1
1
I think it is true, and the proof is roughly this; assuming it is not full rank, then the rows are linearly dependent. This linear dependence gives you a recurrence for $a_n$ with a smaller value of $d$, contradiction.
– Mike Earnest
Aug 27 at 19:46
I think it is true, and the proof is roughly this; assuming it is not full rank, then the rows are linearly dependent. This linear dependence gives you a recurrence for $a_n$ with a smaller value of $d$, contradiction.
– Mike Earnest
Aug 27 at 19:46
@MikeEarnest That was my thought as well. I couldn't find a way to make this work, but perhaps I just need to go manipulate some more sums until it happens.
– rwbogl
Aug 27 at 20:10
@MikeEarnest That was my thought as well. I couldn't find a way to make this work, but perhaps I just need to go manipulate some more sums until it happens.
– rwbogl
Aug 27 at 20:10
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Assuming it is not full rank, then the columns $defabf aa_i$ are linearly dependent. Let $sum_i=0^d-1k_ia_i=0$ be a linear dependence, and let $e$ be the largest index for which $k_eneq 0$. Then the $j^th$ row of the recurrence implies that
$$
a_e+j=-frack_e-1k_ea_e+j-1-frack_e-2k_ea_e+j-2-dots -frack_jk_ea_j.
$$
This holds for all $0le j le d-1$. You can then prove by induction that this holds for all $j ge0$, using the original recurrence. Letting $tilde k_i=frac-k_e-ik_e$,
$$
a_e+j=sum_i=1^d c_i a_e+j-istackreltextind=sum_i=1^d c_i sum_h=1^etilde k_ha_e+j-i-h=sum_h=1^etilde k_hsum_i=1^dc_ia_e+j-i-h=sum_h=1^etilde k_h a_e+j-h.
$$
We use the inductive hypothesis for the previous $e< d$ cases in $stackreltextind=$, which is OK because there were $d$ base cases.
Finally, $a_e+j=sum_h=1^etilde k_h a_e+j-h$ shows $a_n$ satisfies an $e$ order recurrence, which contradicts the minimality of $d$.
answered Aug 28 at 19:35
Mike Earnest
17.4k11749
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Assuming it is not full rank, then the columns $defabf aa_i$ are linearly dependent. Let $sum_i=0^d-1k_ia_i=0$ be a linear dependence, and let $e$ be the largest index for which $k_eneq 0$. Then the $j^th$ row of the recurrence implies that
$$
a_e+j=-frack_e-1k_ea_e+j-1-frack_e-2k_ea_e+j-2-dots -frack_jk_ea_j.
$$
This holds for all $0le j le d-1$. You can then prove by induction that this holds for all $j ge0$, using the original recurrence. Letting $tilde k_i=frac-k_e-ik_e$,
$$
a_e+j=sum_i=1^d c_i a_e+j-istackreltextind=sum_i=1^d c_i sum_h=1^etilde k_ha_e+j-i-h=sum_h=1^etilde k_hsum_i=1^dc_ia_e+j-i-h=sum_h=1^etilde k_h a_e+j-h.
$$
We use the inductive hypothesis for the previous $e< d$ cases in $stackreltextind=$, which is OK because there were $d$ base cases.
Finally, $a_e+j=sum_h=1^etilde k_h a_e+j-h$ shows $a_n$ satisfies an $e$ order recurrence, which contradicts the minimality of $d$.
answered Aug 28 at 19:35
Mike Earnest
17.4k11749
add a comment |Â
up vote
1
down vote
accepted
Assuming it is not full rank, then the columns $defabf aa_i$ are linearly dependent. Let $sum_i=0^d-1k_ia_i=0$ be a linear dependence, and let $e$ be the largest index for which $k_eneq 0$. Then the $j^th$ row of the recurrence implies that
$$
a_e+j=-frack_e-1k_ea_e+j-1-frack_e-2k_ea_e+j-2-dots -frack_jk_ea_j.
$$
This holds for all $0le j le d-1$. You can then prove by induction that this holds for all $j ge0$, using the original recurrence. Letting $tilde k_i=frac-k_e-ik_e$,
$$
a_e+j=sum_i=1^d c_i a_e+j-istackreltextind=sum_i=1^d c_i sum_h=1^etilde k_ha_e+j-i-h=sum_h=1^etilde k_hsum_i=1^dc_ia_e+j-i-h=sum_h=1^etilde k_h a_e+j-h.
$$
We use the inductive hypothesis for the previous $e< d$ cases in $stackreltextind=$, which is OK because there were $d$ base cases.
Finally, $a_e+j=sum_h=1^etilde k_h a_e+j-h$ shows $a_n$ satisfies an $e$ order recurrence, which contradicts the minimality of $d$.
answered Aug 28 at 19:35
Mike Earnest
17.4k11749
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Assuming it is not full rank, then the columns $defabf aa_i$ are linearly dependent. Let $sum_i=0^d-1k_ia_i=0$ be a linear dependence, and let $e$ be the largest index for which $k_eneq 0$. Then the $j^th$ row of the recurrence implies that
$$
a_e+j=-frack_e-1k_ea_e+j-1-frack_e-2k_ea_e+j-2-dots -frack_jk_ea_j.
$$
This holds for all $0le j le d-1$. You can then prove by induction that this holds for all $j ge0$, using the original recurrence. Letting $tilde k_i=frac-k_e-ik_e$,
$$
a_e+j=sum_i=1^d c_i a_e+j-istackreltextind=sum_i=1^d c_i sum_h=1^etilde k_ha_e+j-i-h=sum_h=1^etilde k_hsum_i=1^dc_ia_e+j-i-h=sum_h=1^etilde k_h a_e+j-h.
$$
We use the inductive hypothesis for the previous $e< d$ cases in $stackreltextind=$, which is OK because there were $d$ base cases.
Finally, $a_e+j=sum_h=1^etilde k_h a_e+j-h$ shows $a_n$ satisfies an $e$ order recurrence, which contradicts the minimality of $d$.
answered Aug 28 at 19:35
Mike Earnest
17.4k11749
Assuming it is not full rank, then the columns $defabf aa_i$ are linearly dependent. Let $sum_i=0^d-1k_ia_i=0$ be a linear dependence, and let $e$ be the largest index for which $k_eneq 0$. Then the $j^th$ row of the recurrence implies that
$$
a_e+j=-frack_e-1k_ea_e+j-1-frack_e-2k_ea_e+j-2-dots -frack_jk_ea_j.
$$
This holds for all $0le j le d-1$. You can then prove by induction that this holds for all $j ge0$, using the original recurrence. Letting $tilde k_i=frac-k_e-ik_e$,
$$
a_e+j=sum_i=1^d c_i a_e+j-istackreltextind=sum_i=1^d c_i sum_h=1^etilde k_ha_e+j-i-h=sum_h=1^etilde k_hsum_i=1^dc_ia_e+j-i-h=sum_h=1^etilde k_h a_e+j-h.
$$
We use the inductive hypothesis for the previous $e< d$ cases in $stackreltextind=$, which is OK because there were $d$ base cases.
Finally, $a_e+j=sum_h=1^etilde k_h a_e+j-h$ shows $a_n$ satisfies an $e$ order recurrence, which contradicts the minimality of $d$.
answered Aug 28 at 19:35
Mike Earnest
17.4k11749
answered Aug 28 at 19:35
Mike Earnest
17.4k11749
answered Aug 28 at 19:35
Mike Earnest
17.4k11749
answered Aug 28 at 19:35
Mike Earnest
17.4k11749
17.4k11749
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2896515%2fis-the-term-matrix-of-a-c-finite-sequence-full-rank%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
I think it is true, and the proof is roughly this; assuming it is not full rank, then the rows are linearly dependent. This linear dependence gives you a recurrence for $a_n$ with a smaller value of $d$, contradiction.
– Mike Earnest
Aug 27 at 19:46
@MikeEarnest That was my thought as well. I couldn't find a way to make this work, but perhaps I just need to go manipulate some more sums until it happens.
– rwbogl
Aug 27 at 20:10