Mixing
Algorithms for Computing the Determinant of a Hankel Matrix
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Consider a $ntimes n$ Hankel Matrix
$$
H = beginbmatrix
x_1 & x_2 & dots & x_n \
x_2 & x_3 & dots & x_n+1 \
vdots \
x_n & x_n+1 & dots & x_2n
endbmatrix
$$
, where all $x_i in mathbbZ_p = 0,dots,p-1 $, where $p$ is prime.
What is the most efficient way to test whether the matrix is invertible or not. More concretely:
Is there a more efficient than computing the determinant?
If not, is there a more efficient way of computing the determinant of such a matrix?
matrices determinant inverse
asked Jul 17 at 16:23
NoKnowledge
1526
add a comment |Â
up vote
2
down vote
favorite
Consider a $ntimes n$ Hankel Matrix
$$
H = beginbmatrix
x_1 & x_2 & dots & x_n \
x_2 & x_3 & dots & x_n+1 \
vdots \
x_n & x_n+1 & dots & x_2n
endbmatrix
$$
, where all $x_i in mathbbZ_p = 0,dots,p-1 $, where $p$ is prime.
What is the most efficient way to test whether the matrix is invertible or not. More concretely:
Is there a more efficient than computing the determinant?
If not, is there a more efficient way of computing the determinant of such a matrix?
matrices determinant inverse
asked Jul 17 at 16:23
NoKnowledge
1526
@littleO how do you say that it is almost circulant if it isn't even Toeplitz?
– Exodd
Jul 17 at 16:55
@Exodd I deleted the comment you were responding to there since it was incorrect.
– littleO
Jul 18 at 12:58
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Consider a $ntimes n$ Hankel Matrix
$$
H = beginbmatrix
x_1 & x_2 & dots & x_n \
x_2 & x_3 & dots & x_n+1 \
vdots \
x_n & x_n+1 & dots & x_2n
endbmatrix
$$
, where all $x_i in mathbbZ_p = 0,dots,p-1 $, where $p$ is prime.
What is the most efficient way to test whether the matrix is invertible or not. More concretely:
Is there a more efficient than computing the determinant?
If not, is there a more efficient way of computing the determinant of such a matrix?
matrices determinant inverse
asked Jul 17 at 16:23
NoKnowledge
1526
Consider a $ntimes n$ Hankel Matrix
$$
H = beginbmatrix
x_1 & x_2 & dots & x_n \
x_2 & x_3 & dots & x_n+1 \
vdots \
x_n & x_n+1 & dots & x_2n
endbmatrix
$$
, where all $x_i in mathbbZ_p = 0,dots,p-1 $, where $p$ is prime.
What is the most efficient way to test whether the matrix is invertible or not. More concretely:
Is there a more efficient than computing the determinant?
If not, is there a more efficient way of computing the determinant of such a matrix?
matrices determinant inverse
asked Jul 17 at 16:23
NoKnowledge
1526
asked Jul 17 at 16:23
NoKnowledge
1526
asked Jul 17 at 16:23
NoKnowledge
1526
asked Jul 17 at 16:23
NoKnowledge
1526
1526
@littleO how do you say that it is almost circulant if it isn't even Toeplitz?
– Exodd
Jul 17 at 16:55
@Exodd I deleted the comment you were responding to there since it was incorrect.
– littleO
Jul 18 at 12:58
add a comment |Â
@littleO how do you say that it is almost circulant if it isn't even Toeplitz?
– Exodd
Jul 17 at 16:55
@Exodd I deleted the comment you were responding to there since it was incorrect.
– littleO
Jul 18 at 12:58
@littleO how do you say that it is almost circulant if it isn't even Toeplitz?
– Exodd
Jul 17 at 16:55
@littleO how do you say that it is almost circulant if it isn't even Toeplitz?
– Exodd
Jul 17 at 16:55
@Exodd I deleted the comment you were responding to there since it was incorrect.
– littleO
Jul 18 at 12:58
@Exodd I deleted the comment you were responding to there since it was incorrect.
– littleO
Jul 18 at 12:58
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
There is an algorithm called Levinson Recursion for Toeplitz matrices which is $mathcalO(n^2)$. There is exists a similar algorithm for Hankel matrices called Hankel Recursion. It appears to be based on the Lanczos algorithm. People don't generally compute determinants the normal way. E.g. they form a matrix decomposition since the following
$$ A = LU implies det(A) = det(LU) =det(L)det(U)$$
after this is done.
$$ det(L)det(U) =prod_i=1^n l_ii prod_i=1^n u_ii $$
Similarly with the QR decomp
$$ A =QR implies det(A) = det(Q)det(R) $$
since the determinant of $ Q $ is 1
$$ det(A) = 1 cdot prod_i=1^n r_ii $$
However, in general, you don't want to use determinant to see if it is invertible. Just extra steps...
answered Jul 17 at 19:17
RHowe
1,010815
Thank you ver much for the link! I will try find and understand what I need from there. What do you mean by your last sentence "you don't want to use the determinant to see if it is invertible." What should I do instead? Solving the system of linear equations is basically as expensive at the very least, no?
– NoKnowledge
Jul 17 at 19:30
@NoKnowledge do you have to use the determinant? The standard time complexity for determinants is $ mathcalO(n!)$ they actually solve the system before hand and then the determinant to my understanding. So if you want to simply check if a system is invertible the fastest way it be similar to the cholesky decomp as hankel matrices are symmetric.
– RHowe
Jul 17 at 19:34
No I don't have to use anything. I just thought this may be a good approach. I just need some method to determine, whether the matrix is invertible or not. I need no other information about the matrix.
– NoKnowledge
Jul 17 at 19:35
@NoKnowledge I think like the other person said there are technically faster methods based on the FFT but I have no idea how to implement them. It would take some searching.
– RHowe
Jul 17 at 19:37
One thing I noticed is that we are working in $mathbb Z_p$, which is a little different than what I'm used to as I have an applied math background. But I bet the FFT ideas are also applicable in this setting.
– littleO
Jul 18 at 0:14
 |Â
show 1 more comment
up vote
0
down vote
This is not a full answer, but it's too long for a comment. The Hankel matrix
$$
H = beginbmatrix x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endbmatrix
$$
can be enlarged to an anti-circulant matrix
$$
tilde H =
left[
beginarrayc
beginarrayc c c c
x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endarray
&
beginarrayc c c
x_5 & x_6 & x_7 \
x_6 & x_7 & x_1 \
x_7 & x_1 & x_2 \
x_1 & x_2 & x_3\
endarray
\
hline
beginarrayc c c c
x_5 & x_6 & x_7 & x_1 \
x_6 & x_7 & x_1 & x_2 \
x_7 & x_1 & x_2 & x_3 \
endarray
&
beginarrayc c c
x_2 & x_3 & x_4 \
x_3 & x_4 & x_5 \
x_4 & x_5 & x_6\
endarray
endarray
right].
$$
I think some discrete Fourier transform techniques are available to perform computations with anti-circulant matrices efficiently. See this post for example: https://math.stackexchange.com/a/1377399/40119
Perhaps this would help with computations involving $H$, though I'm not certain.
answered Jul 17 at 17:24
littleO
26.2k540102
what are exactly the requirements to call a matrix circulant? What do you mean exactly by "it is diagonalized by the discrete Fourier basis"? What is the relation between the determinant of this matrix and the hankel matrix we started with?
– NoKnowledge
Jul 17 at 18:44
that is not a circulant matrix..
– Exodd
Jul 18 at 11:37
@Exodd Oh, thanks, good point. The linear transformation $z mapsto tilde H z$ is not shift-invariant. I edited to use the term anti-circulant instead.
– littleO
Jul 18 at 12:55
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
There is an algorithm called Levinson Recursion for Toeplitz matrices which is $mathcalO(n^2)$. There is exists a similar algorithm for Hankel matrices called Hankel Recursion. It appears to be based on the Lanczos algorithm. People don't generally compute determinants the normal way. E.g. they form a matrix decomposition since the following
$$ A = LU implies det(A) = det(LU) =det(L)det(U)$$
after this is done.
$$ det(L)det(U) =prod_i=1^n l_ii prod_i=1^n u_ii $$
Similarly with the QR decomp
$$ A =QR implies det(A) = det(Q)det(R) $$
since the determinant of $ Q $ is 1
$$ det(A) = 1 cdot prod_i=1^n r_ii $$
However, in general, you don't want to use determinant to see if it is invertible. Just extra steps...
answered Jul 17 at 19:17
RHowe
1,010815
Thank you ver much for the link! I will try find and understand what I need from there. What do you mean by your last sentence "you don't want to use the determinant to see if it is invertible." What should I do instead? Solving the system of linear equations is basically as expensive at the very least, no?
– NoKnowledge
Jul 17 at 19:30
@NoKnowledge do you have to use the determinant? The standard time complexity for determinants is $ mathcalO(n!)$ they actually solve the system before hand and then the determinant to my understanding. So if you want to simply check if a system is invertible the fastest way it be similar to the cholesky decomp as hankel matrices are symmetric.
– RHowe
Jul 17 at 19:34
No I don't have to use anything. I just thought this may be a good approach. I just need some method to determine, whether the matrix is invertible or not. I need no other information about the matrix.
– NoKnowledge
Jul 17 at 19:35
@NoKnowledge I think like the other person said there are technically faster methods based on the FFT but I have no idea how to implement them. It would take some searching.
– RHowe
Jul 17 at 19:37
One thing I noticed is that we are working in $mathbb Z_p$, which is a little different than what I'm used to as I have an applied math background. But I bet the FFT ideas are also applicable in this setting.
– littleO
Jul 18 at 0:14
 |Â
show 1 more comment
up vote
1
down vote
There is an algorithm called Levinson Recursion for Toeplitz matrices which is $mathcalO(n^2)$. There is exists a similar algorithm for Hankel matrices called Hankel Recursion. It appears to be based on the Lanczos algorithm. People don't generally compute determinants the normal way. E.g. they form a matrix decomposition since the following
$$ A = LU implies det(A) = det(LU) =det(L)det(U)$$
after this is done.
$$ det(L)det(U) =prod_i=1^n l_ii prod_i=1^n u_ii $$
Similarly with the QR decomp
$$ A =QR implies det(A) = det(Q)det(R) $$
since the determinant of $ Q $ is 1
$$ det(A) = 1 cdot prod_i=1^n r_ii $$
However, in general, you don't want to use determinant to see if it is invertible. Just extra steps...
answered Jul 17 at 19:17
RHowe
1,010815
Thank you ver much for the link! I will try find and understand what I need from there. What do you mean by your last sentence "you don't want to use the determinant to see if it is invertible." What should I do instead? Solving the system of linear equations is basically as expensive at the very least, no?
– NoKnowledge
Jul 17 at 19:30
@NoKnowledge do you have to use the determinant? The standard time complexity for determinants is $ mathcalO(n!)$ they actually solve the system before hand and then the determinant to my understanding. So if you want to simply check if a system is invertible the fastest way it be similar to the cholesky decomp as hankel matrices are symmetric.
– RHowe
Jul 17 at 19:34
No I don't have to use anything. I just thought this may be a good approach. I just need some method to determine, whether the matrix is invertible or not. I need no other information about the matrix.
– NoKnowledge
Jul 17 at 19:35
@NoKnowledge I think like the other person said there are technically faster methods based on the FFT but I have no idea how to implement them. It would take some searching.
– RHowe
Jul 17 at 19:37
One thing I noticed is that we are working in $mathbb Z_p$, which is a little different than what I'm used to as I have an applied math background. But I bet the FFT ideas are also applicable in this setting.
– littleO
Jul 18 at 0:14
 |Â
show 1 more comment
up vote
1
down vote
up vote
1
down vote
There is an algorithm called Levinson Recursion for Toeplitz matrices which is $mathcalO(n^2)$. There is exists a similar algorithm for Hankel matrices called Hankel Recursion. It appears to be based on the Lanczos algorithm. People don't generally compute determinants the normal way. E.g. they form a matrix decomposition since the following
$$ A = LU implies det(A) = det(LU) =det(L)det(U)$$
after this is done.
$$ det(L)det(U) =prod_i=1^n l_ii prod_i=1^n u_ii $$
Similarly with the QR decomp
$$ A =QR implies det(A) = det(Q)det(R) $$
since the determinant of $ Q $ is 1
$$ det(A) = 1 cdot prod_i=1^n r_ii $$
However, in general, you don't want to use determinant to see if it is invertible. Just extra steps...
answered Jul 17 at 19:17
RHowe
1,010815
There is an algorithm called Levinson Recursion for Toeplitz matrices which is $mathcalO(n^2)$. There is exists a similar algorithm for Hankel matrices called Hankel Recursion. It appears to be based on the Lanczos algorithm. People don't generally compute determinants the normal way. E.g. they form a matrix decomposition since the following
$$ A = LU implies det(A) = det(LU) =det(L)det(U)$$
after this is done.
$$ det(L)det(U) =prod_i=1^n l_ii prod_i=1^n u_ii $$
Similarly with the QR decomp
$$ A =QR implies det(A) = det(Q)det(R) $$
since the determinant of $ Q $ is 1
$$ det(A) = 1 cdot prod_i=1^n r_ii $$
However, in general, you don't want to use determinant to see if it is invertible. Just extra steps...
answered Jul 17 at 19:17
RHowe
1,010815
answered Jul 17 at 19:17
RHowe
1,010815
answered Jul 17 at 19:17
RHowe
1,010815
answered Jul 17 at 19:17
RHowe
1,010815
1,010815
Thank you ver much for the link! I will try find and understand what I need from there. What do you mean by your last sentence "you don't want to use the determinant to see if it is invertible." What should I do instead? Solving the system of linear equations is basically as expensive at the very least, no?
– NoKnowledge
Jul 17 at 19:30
@NoKnowledge do you have to use the determinant? The standard time complexity for determinants is $ mathcalO(n!)$ they actually solve the system before hand and then the determinant to my understanding. So if you want to simply check if a system is invertible the fastest way it be similar to the cholesky decomp as hankel matrices are symmetric.
– RHowe
Jul 17 at 19:34
No I don't have to use anything. I just thought this may be a good approach. I just need some method to determine, whether the matrix is invertible or not. I need no other information about the matrix.
– NoKnowledge
Jul 17 at 19:35
@NoKnowledge I think like the other person said there are technically faster methods based on the FFT but I have no idea how to implement them. It would take some searching.
– RHowe
Jul 17 at 19:37
One thing I noticed is that we are working in $mathbb Z_p$, which is a little different than what I'm used to as I have an applied math background. But I bet the FFT ideas are also applicable in this setting.
– littleO
Jul 18 at 0:14
 |Â
show 1 more comment
Thank you ver much for the link! I will try find and understand what I need from there. What do you mean by your last sentence "you don't want to use the determinant to see if it is invertible." What should I do instead? Solving the system of linear equations is basically as expensive at the very least, no?
– NoKnowledge
Jul 17 at 19:30
@NoKnowledge do you have to use the determinant? The standard time complexity for determinants is $ mathcalO(n!)$ they actually solve the system before hand and then the determinant to my understanding. So if you want to simply check if a system is invertible the fastest way it be similar to the cholesky decomp as hankel matrices are symmetric.
– RHowe
Jul 17 at 19:34
No I don't have to use anything. I just thought this may be a good approach. I just need some method to determine, whether the matrix is invertible or not. I need no other information about the matrix.
– NoKnowledge
Jul 17 at 19:35
@NoKnowledge I think like the other person said there are technically faster methods based on the FFT but I have no idea how to implement them. It would take some searching.
– RHowe
Jul 17 at 19:37
One thing I noticed is that we are working in $mathbb Z_p$, which is a little different than what I'm used to as I have an applied math background. But I bet the FFT ideas are also applicable in this setting.
– littleO
Jul 18 at 0:14
Thank you ver much for the link! I will try find and understand what I need from there. What do you mean by your last sentence "you don't want to use the determinant to see if it is invertible." What should I do instead? Solving the system of linear equations is basically as expensive at the very least, no?
– NoKnowledge
Jul 17 at 19:30
Thank you ver much for the link! I will try find and understand what I need from there. What do you mean by your last sentence "you don't want to use the determinant to see if it is invertible." What should I do instead? Solving the system of linear equations is basically as expensive at the very least, no?
– NoKnowledge
Jul 17 at 19:30
@NoKnowledge do you have to use the determinant? The standard time complexity for determinants is $ mathcalO(n!)$ they actually solve the system before hand and then the determinant to my understanding. So if you want to simply check if a system is invertible the fastest way it be similar to the cholesky decomp as hankel matrices are symmetric.
– RHowe
Jul 17 at 19:34
@NoKnowledge do you have to use the determinant? The standard time complexity for determinants is $ mathcalO(n!)$ they actually solve the system before hand and then the determinant to my understanding. So if you want to simply check if a system is invertible the fastest way it be similar to the cholesky decomp as hankel matrices are symmetric.
– RHowe
Jul 17 at 19:34
No I don't have to use anything. I just thought this may be a good approach. I just need some method to determine, whether the matrix is invertible or not. I need no other information about the matrix.
– NoKnowledge
Jul 17 at 19:35
No I don't have to use anything. I just thought this may be a good approach. I just need some method to determine, whether the matrix is invertible or not. I need no other information about the matrix.
– NoKnowledge
Jul 17 at 19:35
@NoKnowledge I think like the other person said there are technically faster methods based on the FFT but I have no idea how to implement them. It would take some searching.
– RHowe
Jul 17 at 19:37
@NoKnowledge I think like the other person said there are technically faster methods based on the FFT but I have no idea how to implement them. It would take some searching.
– RHowe
Jul 17 at 19:37
One thing I noticed is that we are working in $mathbb Z_p$, which is a little different than what I'm used to as I have an applied math background. But I bet the FFT ideas are also applicable in this setting.
– littleO
Jul 18 at 0:14
One thing I noticed is that we are working in $mathbb Z_p$, which is a little different than what I'm used to as I have an applied math background. But I bet the FFT ideas are also applicable in this setting.
– littleO
Jul 18 at 0:14
 |Â
show 1 more comment
up vote
0
down vote
This is not a full answer, but it's too long for a comment. The Hankel matrix
$$
H = beginbmatrix x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endbmatrix
$$
can be enlarged to an anti-circulant matrix
$$
tilde H =
left[
beginarrayc
beginarrayc c c c
x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endarray
&
beginarrayc c c
x_5 & x_6 & x_7 \
x_6 & x_7 & x_1 \
x_7 & x_1 & x_2 \
x_1 & x_2 & x_3\
endarray
\
hline
beginarrayc c c c
x_5 & x_6 & x_7 & x_1 \
x_6 & x_7 & x_1 & x_2 \
x_7 & x_1 & x_2 & x_3 \
endarray
&
beginarrayc c c
x_2 & x_3 & x_4 \
x_3 & x_4 & x_5 \
x_4 & x_5 & x_6\
endarray
endarray
right].
$$
I think some discrete Fourier transform techniques are available to perform computations with anti-circulant matrices efficiently. See this post for example: https://math.stackexchange.com/a/1377399/40119
Perhaps this would help with computations involving $H$, though I'm not certain.
answered Jul 17 at 17:24
littleO
26.2k540102
what are exactly the requirements to call a matrix circulant? What do you mean exactly by "it is diagonalized by the discrete Fourier basis"? What is the relation between the determinant of this matrix and the hankel matrix we started with?
– NoKnowledge
Jul 17 at 18:44
that is not a circulant matrix..
– Exodd
Jul 18 at 11:37
@Exodd Oh, thanks, good point. The linear transformation $z mapsto tilde H z$ is not shift-invariant. I edited to use the term anti-circulant instead.
– littleO
Jul 18 at 12:55
add a comment |Â
up vote
0
down vote
This is not a full answer, but it's too long for a comment. The Hankel matrix
$$
H = beginbmatrix x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endbmatrix
$$
can be enlarged to an anti-circulant matrix
$$
tilde H =
left[
beginarrayc
beginarrayc c c c
x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endarray
&
beginarrayc c c
x_5 & x_6 & x_7 \
x_6 & x_7 & x_1 \
x_7 & x_1 & x_2 \
x_1 & x_2 & x_3\
endarray
\
hline
beginarrayc c c c
x_5 & x_6 & x_7 & x_1 \
x_6 & x_7 & x_1 & x_2 \
x_7 & x_1 & x_2 & x_3 \
endarray
&
beginarrayc c c
x_2 & x_3 & x_4 \
x_3 & x_4 & x_5 \
x_4 & x_5 & x_6\
endarray
endarray
right].
$$
I think some discrete Fourier transform techniques are available to perform computations with anti-circulant matrices efficiently. See this post for example: https://math.stackexchange.com/a/1377399/40119
Perhaps this would help with computations involving $H$, though I'm not certain.
answered Jul 17 at 17:24
littleO
26.2k540102
what are exactly the requirements to call a matrix circulant? What do you mean exactly by "it is diagonalized by the discrete Fourier basis"? What is the relation between the determinant of this matrix and the hankel matrix we started with?
– NoKnowledge
Jul 17 at 18:44
that is not a circulant matrix..
– Exodd
Jul 18 at 11:37
@Exodd Oh, thanks, good point. The linear transformation $z mapsto tilde H z$ is not shift-invariant. I edited to use the term anti-circulant instead.
– littleO
Jul 18 at 12:55
add a comment |Â
up vote
0
down vote
up vote
0
down vote
This is not a full answer, but it's too long for a comment. The Hankel matrix
$$
H = beginbmatrix x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endbmatrix
$$
can be enlarged to an anti-circulant matrix
$$
tilde H =
left[
beginarrayc
beginarrayc c c c
x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endarray
&
beginarrayc c c
x_5 & x_6 & x_7 \
x_6 & x_7 & x_1 \
x_7 & x_1 & x_2 \
x_1 & x_2 & x_3\
endarray
\
hline
beginarrayc c c c
x_5 & x_6 & x_7 & x_1 \
x_6 & x_7 & x_1 & x_2 \
x_7 & x_1 & x_2 & x_3 \
endarray
&
beginarrayc c c
x_2 & x_3 & x_4 \
x_3 & x_4 & x_5 \
x_4 & x_5 & x_6\
endarray
endarray
right].
$$
I think some discrete Fourier transform techniques are available to perform computations with anti-circulant matrices efficiently. See this post for example: https://math.stackexchange.com/a/1377399/40119
Perhaps this would help with computations involving $H$, though I'm not certain.
answered Jul 17 at 17:24
littleO
26.2k540102
This is not a full answer, but it's too long for a comment. The Hankel matrix
$$
H = beginbmatrix x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endbmatrix
$$
can be enlarged to an anti-circulant matrix
$$
tilde H =
left[
beginarrayc
beginarrayc c c c
x_1 & x_2 & x_3 & x_4 \
x_2 & x_3 & x_4 & x_5 \
x_3 & x_4 & x_5 & x_6 \
x_4 & x_5 & x_6 & x_7 \
endarray
&
beginarrayc c c
x_5 & x_6 & x_7 \
x_6 & x_7 & x_1 \
x_7 & x_1 & x_2 \
x_1 & x_2 & x_3\
endarray
\
hline
beginarrayc c c c
x_5 & x_6 & x_7 & x_1 \
x_6 & x_7 & x_1 & x_2 \
x_7 & x_1 & x_2 & x_3 \
endarray
&
beginarrayc c c
x_2 & x_3 & x_4 \
x_3 & x_4 & x_5 \
x_4 & x_5 & x_6\
endarray
endarray
right].
$$
I think some discrete Fourier transform techniques are available to perform computations with anti-circulant matrices efficiently. See this post for example: https://math.stackexchange.com/a/1377399/40119
Perhaps this would help with computations involving $H$, though I'm not certain.
answered Jul 17 at 17:24
littleO
26.2k540102
edited Jul 18 at 12:53
answered Jul 17 at 17:24
littleO
26.2k540102
answered Jul 17 at 17:24
littleO
26.2k540102
answered Jul 17 at 17:24
littleO
26.2k540102
26.2k540102
what are exactly the requirements to call a matrix circulant? What do you mean exactly by "it is diagonalized by the discrete Fourier basis"? What is the relation between the determinant of this matrix and the hankel matrix we started with?
– NoKnowledge
Jul 17 at 18:44
that is not a circulant matrix..
– Exodd
Jul 18 at 11:37
@Exodd Oh, thanks, good point. The linear transformation $z mapsto tilde H z$ is not shift-invariant. I edited to use the term anti-circulant instead.
– littleO
Jul 18 at 12:55
add a comment |Â
what are exactly the requirements to call a matrix circulant? What do you mean exactly by "it is diagonalized by the discrete Fourier basis"? What is the relation between the determinant of this matrix and the hankel matrix we started with?
– NoKnowledge
Jul 17 at 18:44
that is not a circulant matrix..
– Exodd
Jul 18 at 11:37
@Exodd Oh, thanks, good point. The linear transformation $z mapsto tilde H z$ is not shift-invariant. I edited to use the term anti-circulant instead.
– littleO
Jul 18 at 12:55
what are exactly the requirements to call a matrix circulant? What do you mean exactly by "it is diagonalized by the discrete Fourier basis"? What is the relation between the determinant of this matrix and the hankel matrix we started with?
– NoKnowledge
Jul 17 at 18:44
what are exactly the requirements to call a matrix circulant? What do you mean exactly by "it is diagonalized by the discrete Fourier basis"? What is the relation between the determinant of this matrix and the hankel matrix we started with?
– NoKnowledge
Jul 17 at 18:44
that is not a circulant matrix..
– Exodd
Jul 18 at 11:37
that is not a circulant matrix..
– Exodd
Jul 18 at 11:37
@Exodd Oh, thanks, good point. The linear transformation $z mapsto tilde H z$ is not shift-invariant. I edited to use the term anti-circulant instead.
– littleO
Jul 18 at 12:55
@Exodd Oh, thanks, good point. The linear transformation $z mapsto tilde H z$ is not shift-invariant. I edited to use the term anti-circulant instead.
– littleO
Jul 18 at 12:55
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%2f2854671%2falgorithms-for-computing-the-determinant-of-a-hankel-matrix%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
@littleO how do you say that it is almost circulant if it isn't even Toeplitz?
– Exodd
Jul 17 at 16:55
@Exodd I deleted the comment you were responding to there since it was incorrect.
– littleO
Jul 18 at 12:58