2
$\begingroup$

For simplicity, i focus on a particular Toeplitz symmetric matrix, so let $A_{ij} = a^{|i-j|}$ for $i,j=1,\dots,n$ and $0<a<1$ be a Kac-Murdock-Szegő (KMS) matrix, e.g., for n=4

\begin{equation} A = \left[ \begin{matrix} 1 & a & a^2 & a^3 \\ a & 1 & a & a^2 \\ a^2 & a & 1 & a \\ a^3 & a^2 & a & 1 \end{matrix} \right] \end{equation} Consider the following matrix $A_1$ obtained from $A$ setting to zero both the subdiagonal and the superdiagonal as \begin{equation} A_1 = \left[ \begin{matrix} 1 & 0 & a^2 & a^3 \\ 0 & 1 & 0 & a^2 \\ a^2 & 0 & 1 & 0 \\ a^3 & a^2 & 0 & 1 \end{matrix} \right] \end{equation} when $a$ is chosen so that $A_1$ is definite positive, we have $\det(A) < \det(A_1)$. Continuing (under the def.positive assumption) nulling the other additional off diagonals elements we obtain \begin{equation} A_2 = \left[ \begin{matrix} 1 & 0 & 0 & a^3 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ a^3 & 0 & 0 & 1 \end{matrix} \right] \end{equation} Hence, we have $(1-a^2)^3 =\det(A) < \det(A_1)<\det(A_2) < 1$, intuitively increasing the sparsity of the matrix its determinant goes to 1.

My question is: how this fact can be proved, or alternatively to establish that $(1-a^2)^{(n-1)}$ is the minimum value attained by the determinant of the above defined matrices $A_1, A_2, \cdots A_{n-1}$ ?

$\endgroup$
2
  • 1
    $\begingroup$ Something is strange: if $A_1$ (or $A_k$) can cross into non-positive domain, then at the moment of crossing the determinant is zero, so the inequality you propose fails. So either they are all positive definite for $0<a<1$ (and the corresponding requirement is automatic), or the conjectured inequality fails. However if $A=\begin{bmatrix}1&0&1&1\\0&1&0&1\\1&0&1&0\\1&1&0&1\end{bmatrix}$ and $x=[1,1,-1,-1]$, then $(Ax,x)=-2<0$, so we are already way out of positive definite domain. What am I missing? $\endgroup$
    – fedja
    Nov 30, 2021 at 1:57
  • $\begingroup$ Thanks for your comment, actually i miss the assumption that A is strictly diagonally dominant, otherwise it fails to be definite positive $\endgroup$ Nov 30, 2021 at 15:03

1 Answer 1

2
$\begingroup$

Let us compute and plot the functions of the parameter $a$ defined as the determinants of the matrices $A_0$, $A_1$, $A_2$, $A_3$: $$ \begin{aligned} \det A_0 &= \begin{vmatrix}1&a&a^2&a^3\\a&1&a&a^2\\a^2&a&1&a\\a^3&a^2&a&1\end{vmatrix} = 1-3a^2+3a^4-a^6=(1-a)^3(1+a)^3 \ ,\\[2mm] \det A_1 &= \begin{vmatrix}1&0&a^2&a^3\\0&1&0&a^2\\a^2&0&1&0\\a^3&a^2&0&1\end{vmatrix} = 1-2a^4+a^8-a^6 =(1-a^3-a^4)(1+a^3-a^4) \ ,\\[2mm] \det A_2 &= \begin{vmatrix}1&0&0&a^3\\0&1&0&0\\0&0&1&0\\a^3&0&0&1\end{vmatrix} = 1-a^6=(1-a)(1+a)(1-a+a^2)(1+a+a^2) \ ,\\[2mm] \det A_3 &= \begin{vmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{vmatrix} =1 \ . \end{aligned} $$ A plot of these functions of $a\in(0,1)$ is:

Picture for the graphs of \det A_j for N=4

So the claimed inequality $(1-a^2)^3=\det A_0(a)\le \det A_1(a)\le\det A_2(a)\le \det A_3(a)=1$ is valid for $n=4$ only in some neighborhood of zero.

Alternatively, let us consider the case $n=11$.

Picture for the graphs of \det A_j for N=11


So let us consider only the functions in a neighborhood of zero. In $a=0$ all determinants of the $n\times n$-matrices $A_j(a)$ are one. Then it is enough to figure out the first non-trivial term in $a,a^2,a^3,\dots$ in the Taylor expansion of $\det A_j(a)$, $j$ running from $0$ to $n-1$. It turns out that we have: $$\tag{$\dagger$}$$ $$ \begin{aligned} \det A_0(a) &= 1 -(n-1)a^2 + O(a^4)\ ,\\ \det A_1(a) &= 1 -(n-2)a^4 + O(a^6)\ ,\\ \det A_2(a) &= 1 -(n-3)a^6 + O(a^8)\ ,\\ &\text{ and so on }\\ \det A_{j-1}(a) &= 1 -(n-j)a^{2j} + O(a^{2(j+1)})\ ,\\ &\text{ till finally we have}\\ \det A_{n-2}(a) &= 1-a^{2(n-1)}\ ,\\ \det A_{n-1}(a) &= 1\ . \end{aligned} $$ To see this, consider the matrix $A_{j-1}(a)$, $$ A_{j-1}(a)= \begin{bmatrix} 1 &0&0&\dots&0&a^j&a^{j+1}&\dots\\ 0&1 &0&0&\dots&0&a^j&\ddots\\ 0&0&1 &0&0&\dots&0&\ddots\\ \vdots&0&0&1&0&0&0&\ddots\\ 0&\vdots&0&0&1&0&0&\ddots\\ a^j&0&\vdots&0&0&1&0&\ddots\\ a^{j+1}&a^j&0&\vdots&0&0&1&\ddots\\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots\\ \end{bmatrix} $$ Its determinant is a sum of terms corresponding to permutations in the symmetric group $S(n)$ with $n!$ elements. Excepting $1$ (corresponding to the trivial permutation), there is no term in degree $<2j$. To obtain terms in degree $a^{2j}$ we need a permutation that takes from each row (column) a non-zero entry, and two of these entries are $a^j$, all other must be diagonal ones. So it is a transposition, one among $(1,j+1)$, $(2,j+2)$, ... $(n-j,n)$. And there is no chance to produce $(\pm 1)^{n-2}\cdot a^j\cdot a^{j+1}$ using other permutations. This shows $(\dagger)$.

$\square$


Sage code used to produce the graphs:

def A(n, k, a):
    return matrix(n, n, [ 0 if j != jj and abs(j-jj) <= k 
                          else a^abs(j-jj) 
                          for j in range(n) for jj in range(n)])

def mygraphs(N):
    P = plot([])
    for j in range(N):
        P += plot( lambda s: A(N, j, s).det() , (0, 1)
                   , color=((j+1)^2/N^2, (j+1)/N, 1-j/N)
                   , legend_label=f'{j}' )
    return P

mygraphs(4)
mygraphs(11)
$\endgroup$
2
  • $\begingroup$ Thanks a lot for the exhaustive answer! So if i get this right, the proposed inequality works as long as "a" is close enough to zero. I miss some details about how obtaining the term $a^{2j}$, but probably it's my fault. $\endgroup$ Nov 30, 2021 at 22:04
  • $\begingroup$ Yes, near zero the inequality is valid. For the computation of the determinants, this should be simple. For a matrix $X$ of shape $n\times n$ we have $$\det X=\sum_{\sigma\in S(n)}\pm x_{1\sigma(1)}x_{2\sigma(2)}\dots x_{n\sigma(n)}\ ,$$the sign of the term involving $\sigma$ being the sign of the permutation $\sigma$. For the matrix $A_{j-a}(a)$ products obtained from this expansion have some diagonal-$1$-factors (if any) and else only factors $a^M$ with $M\ge j$ that must come from different rows and columns. $1=1^n$ comes from diagonal. $a^{2j}$ from two diagonally reflected $a^j$'s. $\endgroup$
    – dan_fulea
    Dec 1, 2021 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.