Decision procedure on linear transformations of integer vectors. Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Relationship between coordinate systems and linear transformationsLinear Transformation Reflection Equationlinearly independent commuting $2times 2$ complex matrices (Hoffman Kunzze, Linear algebra, 6.5.2)Determine matrix A from linear transformationsLinear Independence of a set of Complex VectorsLinear Transformations in Linear AlgebraWriting the collection of all linear relations between the vectors?Linear Transformations in Linear Alglinear algebra- linear transformationsSimilar Matrices Confer Equivalent Linear Transformations
Did pre-Columbian Americans know the spherical shape of the Earth?
Pointing to problems without suggesting solutions
How do you write "wild blueberries flavored"?
Understanding piped commands in GNU/Linux
.bashrc alias for a command with fixed second parameter
What is a more techy Technical Writer job title that isn't cutesy or confusing?
Can two people see the same photon?
What does 丫 mean? 丫是什么意思？
Random body shuffle every night—can we still function?
How do Java 8 default methods hеlp with lambdas?
My mentor says to set image to Fine instead of RAW — how is this different from JPG?
Does a random sequence of vectors span a Hilbert space?
Is it OK to use the testing sample to compare algorithms?
latest version of QGIS fails to edit attribute table of GeoJSON file
Is the time—manner—place ordering of adverbials an oversimplification?
Can gravitational waves pass through a black hole?
How does TikZ render an arc?
Noise in Eigenvalues plot
Did John Wesley plagiarize Matthew Henry...?
Why do C and C++ allow the expression (int) + 4?
An isoperimetric-type inequality inside a cube
Is this Kuo-toa homebrew race balanced?
Find general formula for the terms
Order between one to one functions and their inverses
Decision procedure on linear transformations of integer vectors.
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Relationship between coordinate systems and linear transformationsLinear Transformation Reflection Equationlinearly independent commuting $2times 2$ complex matrices (Hoffman Kunzze, Linear algebra, 6.5.2)Determine matrix A from linear transformationsLinear Independence of a set of Complex VectorsLinear Transformations in Linear AlgebraWriting the collection of all linear relations between the vectors?Linear Transformations in Linear Alglinear algebra- linear transformationsSimilar Matrices Confer Equivalent Linear Transformations
$begingroup$
I have an linear transformation of $k$-vectors of integers, $T$, and a vector of integers $v$. I would like to determine if there is some $n$ such that $T^nv$ is a vector that starts with zero.
$$
exists n:(T^nv)_0 = 0
$$
For example if
$$
T = left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright] \
v = beginbmatrix-4\0\-1\1endbmatrix
$$
then
$$
beginarrayrl
T^4v &= left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^4
beginbmatrix-4\0\-1\1endbmatrix
\ &= left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^3
beginbmatrix-1\-4\1\1endbmatrix
\ &=left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^2
beginbmatrix-1\-1\-3\1endbmatrix
\ &=left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]
beginbmatrix-6\-1\0\1endbmatrix
\ &= beginbmatrixcolorred0\-6\0\1endbmatrix
endarray
$$
So $n=4$. But for the vector
$$
v = beginbmatrix1\1\1\1endbmatrix
$$
There is pretty clearly no $n$ that satisfies (we can use induction to show that all the entries of the vector will remain positive).
I have been trying to come up with a general decision procedure but I have not been able to get much of anywhere.
What procedure could I use to determine if there is such an $n$?
linear-algebra matrices decision-problems
asked Apr 2 at 14:59
Sriotchilism O'ZaicSriotchilism O'Zaic
897630
$endgroup$
add a comment |
$begingroup$
I have an linear transformation of $k$-vectors of integers, $T$, and a vector of integers $v$. I would like to determine if there is some $n$ such that $T^nv$ is a vector that starts with zero.
$$
exists n:(T^nv)_0 = 0
$$
For example if
$$
T = left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright] \
v = beginbmatrix-4\0\-1\1endbmatrix
$$
then
$$
beginarrayrl
T^4v &= left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^4
beginbmatrix-4\0\-1\1endbmatrix
\ &= left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^3
beginbmatrix-1\-4\1\1endbmatrix
\ &=left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^2
beginbmatrix-1\-1\-3\1endbmatrix
\ &=left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]
beginbmatrix-6\-1\0\1endbmatrix
\ &= beginbmatrixcolorred0\-6\0\1endbmatrix
endarray
$$
So $n=4$. But for the vector
$$
v = beginbmatrix1\1\1\1endbmatrix
$$
There is pretty clearly no $n$ that satisfies (we can use induction to show that all the entries of the vector will remain positive).
I have been trying to come up with a general decision procedure but I have not been able to get much of anywhere.
What procedure could I use to determine if there is such an $n$?
linear-algebra matrices decision-problems
asked Apr 2 at 14:59
Sriotchilism O'ZaicSriotchilism O'Zaic
897630
$endgroup$
$begingroup$
If 𝑇 is diagonalisable, then your problem is equivalent to verify whether $exists n in mathbbN$ such that $sum_i^kc_ia_i^n=0$, for $c_i, a_i in mathbbC$. I do not know if it is an easy task
$endgroup$
– Alex Silva
Apr 5 at 20:42
$begingroup$
@AlexSilva I'm a little confused. What are $c$ and $a$ here? How are they related to $T$ and $v$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 20:52
$begingroup$
$T^n = PD^nP^-1$. Thus, $(PD^nP^-1)v=[0;u]$. The first row of $PD^n$ is $[p_1lambda_1^n cdots p_klambda_k^n]$, where $lambda_i$ are the diagonal elements of $D$. Now $P^-1v$ is a column vector, say $w$. Then $$[p_1lambda_1^n cdots p_klambda_k^n]w = 0 implies$$ $$sum_i^kc_ilambda_i^n = 0.$$ Actually, $a_i=lambda_i$.
$endgroup$
– Alex Silva
Apr 5 at 21:03
$begingroup$
@AlexSilva Then $c_i=p_i(P^-1v)_i$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 21:30
$begingroup$
Yes! Exactly! :)
$endgroup$
– Alex Silva
Apr 5 at 21:41
add a comment |
$begingroup$
I have an linear transformation of $k$-vectors of integers, $T$, and a vector of integers $v$. I would like to determine if there is some $n$ such that $T^nv$ is a vector that starts with zero.
$$
exists n:(T^nv)_0 = 0
$$
For example if
$$
T = left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright] \
v = beginbmatrix-4\0\-1\1endbmatrix
$$
then
$$
beginarrayrl
T^4v &= left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^4
beginbmatrix-4\0\-1\1endbmatrix
\ &= left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^3
beginbmatrix-1\-4\1\1endbmatrix
\ &=left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^2
beginbmatrix-1\-1\-3\1endbmatrix
\ &=left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]
beginbmatrix-6\-1\0\1endbmatrix
\ &= beginbmatrixcolorred0\-6\0\1endbmatrix
endarray
$$
So $n=4$. But for the vector
$$
v = beginbmatrix1\1\1\1endbmatrix
$$
There is pretty clearly no $n$ that satisfies (we can use induction to show that all the entries of the vector will remain positive).
I have been trying to come up with a general decision procedure but I have not been able to get much of anywhere.
What procedure could I use to determine if there is such an $n$?
linear-algebra matrices decision-problems
asked Apr 2 at 14:59
Sriotchilism O'ZaicSriotchilism O'Zaic
897630
$endgroup$
I have an linear transformation of $k$-vectors of integers, $T$, and a vector of integers $v$. I would like to determine if there is some $n$ such that $T^nv$ is a vector that starts with zero.
$$
exists n:(T^nv)_0 = 0
$$
For example if
$$
T = left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright] \
v = beginbmatrix-4\0\-1\1endbmatrix
$$
then
$$
beginarrayrl
T^4v &= left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^4
beginbmatrix-4\0\-1\1endbmatrix
\ &= left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^3
beginbmatrix-1\-4\1\1endbmatrix
\ &=left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]^2
beginbmatrix-1\-1\-3\1endbmatrix
\ &=left[beginarraycccc
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 1 \
endarrayright]
beginbmatrix-6\-1\0\1endbmatrix
\ &= beginbmatrixcolorred0\-6\0\1endbmatrix
endarray
$$
So $n=4$. But for the vector
$$
v = beginbmatrix1\1\1\1endbmatrix
$$
There is pretty clearly no $n$ that satisfies (we can use induction to show that all the entries of the vector will remain positive).
I have been trying to come up with a general decision procedure but I have not been able to get much of anywhere.
What procedure could I use to determine if there is such an $n$?
linear-algebra matrices decision-problems
linear-algebra matrices decision-problems
asked Apr 2 at 14:59
Sriotchilism O'ZaicSriotchilism O'Zaic
897630
asked Apr 2 at 14:59
Sriotchilism O'ZaicSriotchilism O'Zaic
897630
edited Apr 2 at 21:56
Sriotchilism O'Zaic
asked Apr 2 at 14:59
Sriotchilism O'ZaicSriotchilism O'Zaic
897630
asked Apr 2 at 14:59
Sriotchilism O'ZaicSriotchilism O'Zaic
897630
asked Apr 2 at 14:59
Sriotchilism O'ZaicSriotchilism O'Zaic
897630
897630
$begingroup$
If 𝑇 is diagonalisable, then your problem is equivalent to verify whether $exists n in mathbbN$ such that $sum_i^kc_ia_i^n=0$, for $c_i, a_i in mathbbC$. I do not know if it is an easy task
$endgroup$
– Alex Silva
Apr 5 at 20:42
$begingroup$
@AlexSilva I'm a little confused. What are $c$ and $a$ here? How are they related to $T$ and $v$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 20:52
$begingroup$
$T^n = PD^nP^-1$. Thus, $(PD^nP^-1)v=[0;u]$. The first row of $PD^n$ is $[p_1lambda_1^n cdots p_klambda_k^n]$, where $lambda_i$ are the diagonal elements of $D$. Now $P^-1v$ is a column vector, say $w$. Then $$[p_1lambda_1^n cdots p_klambda_k^n]w = 0 implies$$ $$sum_i^kc_ilambda_i^n = 0.$$ Actually, $a_i=lambda_i$.
$endgroup$
– Alex Silva
Apr 5 at 21:03
$begingroup$
@AlexSilva Then $c_i=p_i(P^-1v)_i$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 21:30
$begingroup$
Yes! Exactly! :)
$endgroup$
– Alex Silva
Apr 5 at 21:41
add a comment |
$begingroup$
If 𝑇 is diagonalisable, then your problem is equivalent to verify whether $exists n in mathbbN$ such that $sum_i^kc_ia_i^n=0$, for $c_i, a_i in mathbbC$. I do not know if it is an easy task
$endgroup$
– Alex Silva
Apr 5 at 20:42
$begingroup$
@AlexSilva I'm a little confused. What are $c$ and $a$ here? How are they related to $T$ and $v$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 20:52
$begingroup$
$T^n = PD^nP^-1$. Thus, $(PD^nP^-1)v=[0;u]$. The first row of $PD^n$ is $[p_1lambda_1^n cdots p_klambda_k^n]$, where $lambda_i$ are the diagonal elements of $D$. Now $P^-1v$ is a column vector, say $w$. Then $$[p_1lambda_1^n cdots p_klambda_k^n]w = 0 implies$$ $$sum_i^kc_ilambda_i^n = 0.$$ Actually, $a_i=lambda_i$.
$endgroup$
– Alex Silva
Apr 5 at 21:03
$begingroup$
@AlexSilva Then $c_i=p_i(P^-1v)_i$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 21:30
$begingroup$
Yes! Exactly! :)
$endgroup$
– Alex Silva
Apr 5 at 21:41
$begingroup$
If 𝑇 is diagonalisable, then your problem is equivalent to verify whether $exists n in mathbbN$ such that $sum_i^kc_ia_i^n=0$, for $c_i, a_i in mathbbC$. I do not know if it is an easy task
$endgroup$
– Alex Silva
Apr 5 at 20:42
$begingroup$
If 𝑇 is diagonalisable, then your problem is equivalent to verify whether $exists n in mathbbN$ such that $sum_i^kc_ia_i^n=0$, for $c_i, a_i in mathbbC$. I do not know if it is an easy task
$endgroup$
– Alex Silva
Apr 5 at 20:42
$begingroup$
@AlexSilva I'm a little confused. What are $c$ and $a$ here? How are they related to $T$ and $v$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 20:52
$begingroup$
@AlexSilva I'm a little confused. What are $c$ and $a$ here? How are they related to $T$ and $v$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 20:52
$begingroup$
$T^n = PD^nP^-1$. Thus, $(PD^nP^-1)v=[0;u]$. The first row of $PD^n$ is $[p_1lambda_1^n cdots p_klambda_k^n]$, where $lambda_i$ are the diagonal elements of $D$. Now $P^-1v$ is a column vector, say $w$. Then $$[p_1lambda_1^n cdots p_klambda_k^n]w = 0 implies$$ $$sum_i^kc_ilambda_i^n = 0.$$ Actually, $a_i=lambda_i$.
$endgroup$
– Alex Silva
Apr 5 at 21:03
$begingroup$
$T^n = PD^nP^-1$. Thus, $(PD^nP^-1)v=[0;u]$. The first row of $PD^n$ is $[p_1lambda_1^n cdots p_klambda_k^n]$, where $lambda_i$ are the diagonal elements of $D$. Now $P^-1v$ is a column vector, say $w$. Then $$[p_1lambda_1^n cdots p_klambda_k^n]w = 0 implies$$ $$sum_i^kc_ilambda_i^n = 0.$$ Actually, $a_i=lambda_i$.
$endgroup$
– Alex Silva
Apr 5 at 21:03
$begingroup$
@AlexSilva Then $c_i=p_i(P^-1v)_i$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 21:30
$begingroup$
@AlexSilva Then $c_i=p_i(P^-1v)_i$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 21:30
$begingroup$
Yes! Exactly! :)
$endgroup$
– Alex Silva
Apr 5 at 21:41
$begingroup$
Yes! Exactly! :)
$endgroup$
– Alex Silva
Apr 5 at 21:41
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Unfortunately, existence of an algorithm for this problem is open.
Here are a few links and partial results:
- Skolem problem at Wikipedia
- Terence Tao's blog: effective Skolem-Mahler-Lech theorem
- Proof that the set is semilinear
- Skolem's Problem - On the Border between Decidability and Undecidability
The problem in those links is stated using a linear recurrence relation, which is equivalent to the matrix formulation (see, for example, lemma 1.1 in the last link)
It definitely feels that there should be an algorithm, but we haven't found it yet. If the input contains multiple matrices $M_1, dots, M_k$ and you're interested whether the product $M_i_1 M_i_2 dots M_i_n$ has a 0 entry in a corner, this is known to be undecidable: see this link about the matrix mortality problem.
answered Apr 6 at 0:00
sdcvvcsdcvvc
8,48312650
$endgroup$
$begingroup$
Wow thanks! That's a bit unfortunate. I haven't read the last two sources in their entirety (I'm going to take a more careful look when I have the time), but I was wondering if you were aware of any large sub-classes for which there are known algorithms.
$endgroup$
– Sriotchilism O'Zaic
Apr 6 at 0:12
1
$begingroup$
I don't know much more about the problem, behind what I could skim from the sources. Wikipedia states that there is a known algorithm for recurrences of degree at most 4 (this probably translates to 4x4 matrices), and additionally it's decidable whether set of $n$'s is finite or infinite; but if it's finite, we can't tell whether it's empty or not.
$endgroup$
– sdcvvc
Apr 6 at 0:19
add a comment |
Your Answer
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%2f3171961%2fdecision-procedure-on-linear-transformations-of-integer-vectors%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$
Unfortunately, existence of an algorithm for this problem is open.
Here are a few links and partial results:
- Skolem problem at Wikipedia
- Terence Tao's blog: effective Skolem-Mahler-Lech theorem
- Proof that the set is semilinear
- Skolem's Problem - On the Border between Decidability and Undecidability
The problem in those links is stated using a linear recurrence relation, which is equivalent to the matrix formulation (see, for example, lemma 1.1 in the last link)
It definitely feels that there should be an algorithm, but we haven't found it yet. If the input contains multiple matrices $M_1, dots, M_k$ and you're interested whether the product $M_i_1 M_i_2 dots M_i_n$ has a 0 entry in a corner, this is known to be undecidable: see this link about the matrix mortality problem.
answered Apr 6 at 0:00
sdcvvcsdcvvc
8,48312650
$endgroup$
$begingroup$
Wow thanks! That's a bit unfortunate. I haven't read the last two sources in their entirety (I'm going to take a more careful look when I have the time), but I was wondering if you were aware of any large sub-classes for which there are known algorithms.
$endgroup$
– Sriotchilism O'Zaic
Apr 6 at 0:12
1
$begingroup$
I don't know much more about the problem, behind what I could skim from the sources. Wikipedia states that there is a known algorithm for recurrences of degree at most 4 (this probably translates to 4x4 matrices), and additionally it's decidable whether set of $n$'s is finite or infinite; but if it's finite, we can't tell whether it's empty or not.
$endgroup$
– sdcvvc
Apr 6 at 0:19
add a comment |
$begingroup$
Unfortunately, existence of an algorithm for this problem is open.
Here are a few links and partial results:
- Skolem problem at Wikipedia
- Terence Tao's blog: effective Skolem-Mahler-Lech theorem
- Proof that the set is semilinear
- Skolem's Problem - On the Border between Decidability and Undecidability
The problem in those links is stated using a linear recurrence relation, which is equivalent to the matrix formulation (see, for example, lemma 1.1 in the last link)
It definitely feels that there should be an algorithm, but we haven't found it yet. If the input contains multiple matrices $M_1, dots, M_k$ and you're interested whether the product $M_i_1 M_i_2 dots M_i_n$ has a 0 entry in a corner, this is known to be undecidable: see this link about the matrix mortality problem.
answered Apr 6 at 0:00
sdcvvcsdcvvc
8,48312650
$endgroup$
$begingroup$
Wow thanks! That's a bit unfortunate. I haven't read the last two sources in their entirety (I'm going to take a more careful look when I have the time), but I was wondering if you were aware of any large sub-classes for which there are known algorithms.
$endgroup$
– Sriotchilism O'Zaic
Apr 6 at 0:12
1
$begingroup$
I don't know much more about the problem, behind what I could skim from the sources. Wikipedia states that there is a known algorithm for recurrences of degree at most 4 (this probably translates to 4x4 matrices), and additionally it's decidable whether set of $n$'s is finite or infinite; but if it's finite, we can't tell whether it's empty or not.
$endgroup$
– sdcvvc
Apr 6 at 0:19
add a comment |
$begingroup$
Unfortunately, existence of an algorithm for this problem is open.
Here are a few links and partial results:
- Skolem problem at Wikipedia
- Terence Tao's blog: effective Skolem-Mahler-Lech theorem
- Proof that the set is semilinear
- Skolem's Problem - On the Border between Decidability and Undecidability
The problem in those links is stated using a linear recurrence relation, which is equivalent to the matrix formulation (see, for example, lemma 1.1 in the last link)
It definitely feels that there should be an algorithm, but we haven't found it yet. If the input contains multiple matrices $M_1, dots, M_k$ and you're interested whether the product $M_i_1 M_i_2 dots M_i_n$ has a 0 entry in a corner, this is known to be undecidable: see this link about the matrix mortality problem.
answered Apr 6 at 0:00
sdcvvcsdcvvc
8,48312650
$endgroup$
Unfortunately, existence of an algorithm for this problem is open.
Here are a few links and partial results:
- Skolem problem at Wikipedia
- Terence Tao's blog: effective Skolem-Mahler-Lech theorem
- Proof that the set is semilinear
- Skolem's Problem - On the Border between Decidability and Undecidability
The problem in those links is stated using a linear recurrence relation, which is equivalent to the matrix formulation (see, for example, lemma 1.1 in the last link)
It definitely feels that there should be an algorithm, but we haven't found it yet. If the input contains multiple matrices $M_1, dots, M_k$ and you're interested whether the product $M_i_1 M_i_2 dots M_i_n$ has a 0 entry in a corner, this is known to be undecidable: see this link about the matrix mortality problem.
answered Apr 6 at 0:00
sdcvvcsdcvvc
8,48312650
edited Apr 6 at 0:09
answered Apr 6 at 0:00
sdcvvcsdcvvc
8,48312650
answered Apr 6 at 0:00
sdcvvcsdcvvc
8,48312650
answered Apr 6 at 0:00
sdcvvcsdcvvc
8,48312650
8,48312650
$begingroup$
Wow thanks! That's a bit unfortunate. I haven't read the last two sources in their entirety (I'm going to take a more careful look when I have the time), but I was wondering if you were aware of any large sub-classes for which there are known algorithms.
$endgroup$
– Sriotchilism O'Zaic
Apr 6 at 0:12
1
$begingroup$
I don't know much more about the problem, behind what I could skim from the sources. Wikipedia states that there is a known algorithm for recurrences of degree at most 4 (this probably translates to 4x4 matrices), and additionally it's decidable whether set of $n$'s is finite or infinite; but if it's finite, we can't tell whether it's empty or not.
$endgroup$
– sdcvvc
Apr 6 at 0:19
add a comment |
$begingroup$
Wow thanks! That's a bit unfortunate. I haven't read the last two sources in their entirety (I'm going to take a more careful look when I have the time), but I was wondering if you were aware of any large sub-classes for which there are known algorithms.
$endgroup$
– Sriotchilism O'Zaic
Apr 6 at 0:12
1
$begingroup$
I don't know much more about the problem, behind what I could skim from the sources. Wikipedia states that there is a known algorithm for recurrences of degree at most 4 (this probably translates to 4x4 matrices), and additionally it's decidable whether set of $n$'s is finite or infinite; but if it's finite, we can't tell whether it's empty or not.
$endgroup$
– sdcvvc
Apr 6 at 0:19
$begingroup$
Wow thanks! That's a bit unfortunate. I haven't read the last two sources in their entirety (I'm going to take a more careful look when I have the time), but I was wondering if you were aware of any large sub-classes for which there are known algorithms.
$endgroup$
– Sriotchilism O'Zaic
Apr 6 at 0:12
$begingroup$
Wow thanks! That's a bit unfortunate. I haven't read the last two sources in their entirety (I'm going to take a more careful look when I have the time), but I was wondering if you were aware of any large sub-classes for which there are known algorithms.
$endgroup$
– Sriotchilism O'Zaic
Apr 6 at 0:12
1
1
$begingroup$
I don't know much more about the problem, behind what I could skim from the sources. Wikipedia states that there is a known algorithm for recurrences of degree at most 4 (this probably translates to 4x4 matrices), and additionally it's decidable whether set of $n$'s is finite or infinite; but if it's finite, we can't tell whether it's empty or not.
$endgroup$
– sdcvvc
Apr 6 at 0:19
$begingroup$
I don't know much more about the problem, behind what I could skim from the sources. Wikipedia states that there is a known algorithm for recurrences of degree at most 4 (this probably translates to 4x4 matrices), and additionally it's decidable whether set of $n$'s is finite or infinite; but if it's finite, we can't tell whether it's empty or not.
$endgroup$
– sdcvvc
Apr 6 at 0:19
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%2f3171961%2fdecision-procedure-on-linear-transformations-of-integer-vectors%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$
If 𝑇 is diagonalisable, then your problem is equivalent to verify whether $exists n in mathbbN$ such that $sum_i^kc_ia_i^n=0$, for $c_i, a_i in mathbbC$. I do not know if it is an easy task
$endgroup$
– Alex Silva
Apr 5 at 20:42
$begingroup$
@AlexSilva I'm a little confused. What are $c$ and $a$ here? How are they related to $T$ and $v$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 20:52
$begingroup$
$T^n = PD^nP^-1$. Thus, $(PD^nP^-1)v=[0;u]$. The first row of $PD^n$ is $[p_1lambda_1^n cdots p_klambda_k^n]$, where $lambda_i$ are the diagonal elements of $D$. Now $P^-1v$ is a column vector, say $w$. Then $$[p_1lambda_1^n cdots p_klambda_k^n]w = 0 implies$$ $$sum_i^kc_ilambda_i^n = 0.$$ Actually, $a_i=lambda_i$.
$endgroup$
– Alex Silva
Apr 5 at 21:03
$begingroup$
@AlexSilva Then $c_i=p_i(P^-1v)_i$?
$endgroup$
– Sriotchilism O'Zaic
Apr 5 at 21:30
$begingroup$
Yes! Exactly! :)
$endgroup$
– Alex Silva
Apr 5 at 21:41