I'm trying to figure out how to make a computer reduce a system of
recurrence relations. I've been looking at maxima because that's all I
have, but I haven't figured it out yet. If someone knows how to do
this with Mathmatica, Maple or anything else I would appreciate that
as well. For example given:

a[n] = 2a[n-1] + 3b[n-1], a[0] = 1
b[n] = a[n-1] + 3b[n-1], a[0] = 0

I want it to give me (solved by hand):

a[n] = 5a[n-1] - 3a[n-2], a[0] = 1, a[1] = 2

I just want to reduce it to one function. Yes, it is easy to do this
example by hand, but for larger systems it becomes tedious and error-
prone to keep track of all the details. I've solved a couple largish
ones by hand, but I'd prefer not to do it again. Thanks for the help!

-----Jay

Thanks you so much. That is exactly what I've been looking for. This
may sound dumb, but I hadn't heard of a characteristic equation of a
matrix before so thanks. It worked perfectly for some bigger systems.
I have more stuff to read about now. Thanks!

with(LinearAlgebra):
A:=Matrix([[1,2],[3,4]]);
[1 2]

CharacteristicPolynomial(A,x);
2

solve(%=0,x);
1/2 1/2

Eigenvalues(A);
[ 1/2]

In article <1174771192.340805.25...@l77g2000hsb.googlegroups.com>,



horndud...@gmail.com> wrote:
I'm trying to figure out how to make a computer reduce a system of
recurrence relations. I've been looking at maxima because that's all I
have, but I haven't figured it out yet. If someone knows how to do
this with Mathmatica, Maple or anything else I would appreciate that
as well. For example given:

a[n] = 2a[n-1] + 3b[n-1], a[0] = 1
b[n] = a[n-1] + 3b[n-1], a[0] = 0

I want it to give me (solved by hand):

a[n] = 5a[n-1] - 3a[n-2], a[0] = 1, a[1] = 2

I just want to reduce it to one function. Yes, it is easy to do this
example by hand, but for larger systems it becomes tedious and error-
prone to keep track of all the details. I've solved a couple largish
ones by hand, but I'd prefer not to do it again. Thanks for the help!

-----Jay

You can use matrices for this. If A(n) is the column matrix
[a[n];b[n]] and T is the matrix [2,3;1,3],
then your two equations become the one matrix equation
A(n) = T A(n-1) .
The result you want to get is basically the characteristic
equation for the matrix T.

--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/

horndud...@gmail.com> wrote in message

news:1174781627.191102.113370@n76g2000hsh.googlegroups.com...

Thanks you so much. That is exactly what I've been looking for. This
may sound dumb, but I hadn't heard of a characteristic equation of a
matrix before so thanks. It worked perfectly for some bigger systems.
I have more stuff to read about now. Thanks!

The charaterstic equation of a matrix is a very importrant object.

By taking the determinant of A-x*I where I is the unit matrix, and x is
parameter (usually written as lambda, but here it is easier to write x), and
setting this determinant to zero, you will get a polynomial or an equation
in x. This polynomial is called the Charaterstic equation (or polynomial)
of the matrix A. It is a poly in lambda.

The roots of this polynomial are the eigenvalues of the matrix.

In Maple, you can see this polynomial using the command
CharatersticPolynomial

with(LinearAlgebra):
A:=Matrix([[1,2],[3,4]]);

[1 2]
A := [ ]
[3 4]

CharacteristicPolynomial(A,x);

2
-2 + x - 5 x> solve(%=0,x);

1/2 1/2
33 33
5/2 + -----, 5/2 - -----
2 2

Eigenvalues(A);

[ 1/2]
[ 33 ]
[5/2 + -----]
[ 2 ]
[ ]
[ 1/2]
[ 33 ]
[5/2 - -----]
[ 2 ]

you see they are the same.

knowing how to find eigenvalues and corresponding eigenvectors of a matrix,
and most importantly, what they really mean physically and geometrically is
one of the corner stones of linear algebra.

hth

Nasser

Thanks for this explanation. I have another question about the
characteristic equation. How do you know if it is minimal? let me
explain. Here is a system of recurrence relations:

a[n] = b[n-1] + c[n-1]
b[n] = d[n-1] + e[n-1]
c[n] = f[n-1] + a[n-1]
d[n] = g[n-1] + c[n-1]
e[n] = h[n-1]
f[n] = c[n-1]
g[n] = a[n-1]
h[n] = i[n-1] + a[n-1]
i[n] = j[n-1]
j[n] = e[n-1]

Here is its associated matrix:

[
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0,
0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
]


I solve for the characteristic equation and get this:

x^10 - 2x^8 - 4x^6 + 4x^4 +2x^2 - 1 = 0

which I can change back into a recurrence relation:

a[n] = 2a[n-2] + 4a[n-4] - 4a[n-6] - 2a[n-8] + a[n-10]

When I solved this by hand I got this answer:

a[n] = a[n-2] + 5a[n-4] + a[n-6] - a[n-8]

These two equations are equivalent (but one is longer):

a[n] - a[n-2] =
a[n-2] + 5a[n-4] + a[n-6] - a[n-8]
- a[n-4] - 5a[n-6] - a[n-8] + a[n-10]
a[n] = 2a[n-2] + 4a[n-4] - 4a[n-6] - 2a[n-8] + a[n-10]

So my question is how do I know if the characteristic equation is
minimal (sorry if I'm not using the correct terminology)? How to I
make sure I get the minimal characteristic equation? If these are
simple questions just tell me to go read a linear algebra book (which
I plan to do anyways). Thanks again!

-----Jay

Thanks for this explanation. I have another question about the
characteristic equation. How do you know if it is minimal?

CharacteristicPolynomial(A,x);

MinimalPolynomial(A,x);

let me
explain. Here is a system of recurrence relations:

a[n] = b[n-1] + c[n-1]
b[n] = d[n-1] + e[n-1]
c[n] = f[n-1] + a[n-1]
d[n] = g[n-1] + c[n-1]
e[n] = h[n-1]
f[n] = c[n-1]
g[n] = a[n-1]
h[n] = i[n-1] + a[n-1]
i[n] = j[n-1]
j[n] = e[n-1]

Here is its associated matrix:

[
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0,
0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
]


I solve for the characteristic equation and get this:

x^10 - 2x^8 - 4x^6 + 4x^4 +2x^2 - 1 = 0

which I can change back into a recurrence relation:

a[n] = 2a[n-2] + 4a[n-4] - 4a[n-6] - 2a[n-8] + a[n-10]

When I solved this by hand I got this answer:

a[n] = a[n-2] + 5a[n-4] + a[n-6] - a[n-8]

These two equations are equivalent (but one is longer):

a[n] - a[n-2] =
a[n-2] + 5a[n-4] + a[n-6] - a[n-8]
- a[n-4] - 5a[n-6] - a[n-8] + a[n-10]
a[n] = 2a[n-2] + 4a[n-4] - 4a[n-6] - 2a[n-8] + a[n-10]

So my question is how do I know if the characteristic equation is
minimal (sorry if I'm not using the correct terminology)? How to I
make sure I get the minimal characteristic equation? If these are
simple questions just tell me to go read a linear algebra book (which
I plan to do anyways). Thanks again!

-----Jay


MinimalPolynomial(A,x);
2

On Mar 24, 7:47 pm, "Nasser Abbasi" <n...@12000.org> wrote:
horndud...@gmail.com> wrote in message

news:1174781627.191102.113370@n76g2000hsh.googlegroups.com...

Thanks you so much. That is exactly what I've been looking for. This
may sound dumb, but I hadn't heard of a characteristic equation of a
matrix before so thanks. It worked perfectly for some bigger systems.
I have more stuff to read about now. Thanks!

The charaterstic equation of a matrix is a very importrant object.

By taking the determinant of A-x*I where I is the unit matrix, and x
is
parameter (usually written as lambda, but here it is easier to write x),
and
setting this determinant to zero, you will get a polynomial or an
equation
in x. This polynomial is called the Charaterstic equation (or
polynomial)
of the matrix A. It is a poly in lambda.

The roots of this polynomial are the eigenvalues of the matrix.

In Maple, you can see this polynomial using the command
CharatersticPolynomial

with(LinearAlgebra):
A:=Matrix([[1,2],[3,4]]);

[1 2]
A := [ ]
[3 4]

CharacteristicPolynomial(A,x);

2
-2 + x - 5 x> solve(%=0,x);

1/2 1/2
33 33
5/2 + -----, 5/2 - -----
2 2

Eigenvalues(A);

[ 1/2]
[ 33 ]
[5/2 + -----]
[ 2 ]
[ ]
[ 1/2]
[ 33 ]
[5/2 - -----]
[ 2 ]

you see they are the same.

knowing how to find eigenvalues and corresponding eigenvectors of a
matrix,
and most importantly, what they really mean physically and geometrically
is
one of the corner stones of linear algebra.

hth

Nasser

a[n] = 2a[n-1] + 3b[n-1], a[0] = 1
b[n] = a[n-1] + 3b[n-1], a[0] = 0
...how to do this with Mathmatica

I'm trying to figure out how to make a computer reduce a system of
recurrence relations. I've been looking at maxima because that's all I
have, but I haven't figured it out yet. If someone knows how to do
this with Mathmatica, Maple or anything else I would appreciate that
as well. For example given:

a[n] = 2a[n-1] + 3b[n-1], a[0] = 1
b[n] = a[n-1] + 3b[n-1], a[0] = 0

I want it to give me (solved by hand):

a[n] = 5a[n-1] - 3a[n-2], a[0] = 1, a[1] = 2

I just want to reduce it to one function. Yes, it is easy to do this
example by hand, but for larger systems it becomes tedious and error-
prone to keep track of all the details. I've solved a couple largish
ones by hand, but I'd prefer not to do it again. Thanks for the help!

-----Jay