Maximum Absolute Determinants of Upper Hessenberg Bohemian Matrices

Jonathan P. Keating Mathematical Institute, University of Oxford, Andrew Wiles Building, Oxford, OX2 6GG, UK ([email protected]) Ahmet Abdullah Keleş Department of Mathematics, Bilkent University, 06800 Bilkent, Ankara, Turkey ([email protected])

Abstract

A matrix is called Bohemian if its entries are sampled from a finite set of integers. We determine the maximum absolute determinant of upper Hessenberg Bohemian Matrices for which the subdiagonal entries are fixed to be $1$ and upper triangular entries are sampled from $\{0,1,\dots,n\}$ , extending previous results for $n=1$ and $n=2$ and proving a recent conjecture of Fasi & Negri Porzio [8]. Furthermore, we generalize the problem to non-integer-valued entries.

keywords:

Upper Hessenberg, Bohemian Matrix, Maximum Absolute Determinant.

{AMS}

11C20, 15A15, 15B36.

1 Introduction

Matrices whose entries are from a small subset of the integers are said to be Bohemian, an abbreviation of BOunded HEight Matrix of integers. These matrices appear in many different contexts, including adjacency matrices of graphs [10], Hadamard matrices [1, 2], random discrete matrices [4] and alternating sign matrices [3]. They have been studied for over a century and remain a subject of active research. The website [7] provides a comprehensive overview of recent results and open problems.

Recently, Chan et al. investigated several properties of the characteristic polynomials of upper Hessenberg Bohemian matrices [5], and Thornton et al. obtained a number of results concerning the distribution of their eigenvalues, characteristic heights, and maximum absolute determinant values [6]. These papers state several conjectures on the values of the determinants of Bohemian matrices [7], many of which have recently been solved and generalised by Massimiliano Fasi and Gian M. N. Porzio [8].

One of these conjectures, which is a refinement of a result of Li Ching [9], was until now lacking a solution that could be generalised. We here provide a generalisable solution for that problem and explore an extension of it. Specifically, we focus on the maximum absolute determinant of upper Hessenberg matrices with fixed subdiagonal entries and a given population $[0,t]$ of upper triangular entries. Our calculations provide a more comprehensive understanding of the behaviour of the determinants of these kind of matrices and include special cases that had previously been solved by other approaches.

2 Results

In 1993, Ching proved the following theorem.

Theorem 2.1.

The maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with upper triangular entries from $\{0,1\}$ and subdiagonal entries fixed at $1$ is given by the Fibonacci sequence. [9]

Recently Fasi and Porzio have established the following theorem, proving a result conjectured by Thornton [7]:

Theorem 2.2.

The maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with upper triangular entries from $\{0,1,2\}$ and subdiagonal entries fixed at $1$ is given by the following sequence. Let $M_{n}$ denote the maximum absolute determinant among these $n\times n$ matrices, then $M_{1}=2$ , $M_{2}=4$ , and $M_{n}=2\cdot M_{n-1}+M_{n-2}$ for all $n\geq 3$ . [8]

It is a natural question what happens if the upper triangular population is $\{0,1,\dots,n\}$ . Fasi and Porzio stated the following conjecture in this context.

Conjecture 2.3.

The maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with upper triangular entries from $\{0,1,\dots,d\}$ and subdiagonal entries fixed at $1$ is given by the following generalized Fibonacci sequence. Let $M_{n}$ denote the maximum absolute determinant among these $n\times n$ matrices, then $M_{1}=d$ , $M_{2}=d^{2}$ , $M_{n}=d\cdot M_{n-1}+M_{n-2}$ for all $n\geq 3$ . [8]

We discuss the following, further generalisation of this problem.

Problem 2.4.

What is the maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with upper triangular entries drawn from $[0,t]$ , $t>0$ , and subdiagonal entries taking a fixed value $s\in\mathbb{R}$ ?

If $s$ is negative the problem is relatively straightforward and the result can be stated as the following theorem, whose proof may be found in [8].

Theorem 2.5.

The maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with upper triangular entries from $[0,t]$ and subdiagonal entries fixed at $s<0$ is given by $t\cdot(t-s)^{n-1}$ for all $n\in\mathbb{N}$ .

However the proof of this theorem does not extend to $s>0$ .

We here solve Problem 2.4 in various regimes when $s>0$ . The first case we consider is when $s\leq t$ , the second is $t\cdot(1+\epsilon)\geq s\geq t$ (where $\epsilon$ is a sufficiently small positive number depending on the dimension of the matrix) and the third case is $s>t\cdot\dfrac{4}{5}\cdot n^{2}$ . Our main results are contained in the following theorems:

Theorem 2.6.

The maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with entries from the interval $[0,t]$ and subdiagonal entries fixed at $s$ , such that $t\geq s>0$ , is given by the following sequence. Let $M_{n}$ denote the maximum absolute determinant among these $n\times n$ matrices; then $M_{1}=t$ , $M_{2}=t^{2}$ and $M_{n}=tM_{n-1}+s^{2}M_{n-2}$ for all $n>2$ in $\mathbb{Z}$ .

Remark 2.7.

Note that the determinant is a linear function with respect to each entry. Hence, for the problem of the matrix with maximum absolute determinant, the cases when the upper triangular population is $\{0,1,\dots,d\}$ and $[0,d]$ are equivalent. So, if we set $t=d\in\mathbb{N}$ and $s=1$ , then we prove Conjecture 2.3 as a corollary of Theorem 2.6.

Theorem 2.8.

The maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with entries from the interval $[0,t]$ , subdiagonal entries fixed at $s$ and $n\geq 4$ such that $t\cdot(1+\epsilon(n))\geq s\geq t$ where $\epsilon(n)$ is a sufficiently small positive number depending on $n$ is given by the following sequence. Let $M_{n}$ denote the maximum absolute determinant among these $n\times n$ matrices; then $M_{4}=3s^{2}t^{2}$ , $M_{5}=s^{4}t+4s^{2}t^{3}$ and $M_{n}=tM_{n-1}+s^{2}M_{n-2}$ for all $n>5$ in $\mathbb{Z}$ .

Theorem 2.9.

The maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with entries from the interval $[0,t]$ and subdiagonal entries fixed at $s$ such that $\dfrac{s}{t}>\dfrac{4}{5}\cdot n^{2}$ is given by $s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}$ .

Throughout this paper we use the following definitions and notation.

Definition 2.10.

The set of all $n\times n$ upper Hessenberg matrices whose subdiagonal entries are fixed at $s$ and upper triangular entries are from the set $P$ is denoted by $\mathcal{G}_{s}^{n\times n}(P)$ .

Definition 2.11.

For a given $n\times n$ matrix $A$ , denote the determinant of the bottom-right $(n+1-k)\times(n+1-k)$ part of $A$ by $H_{k}(A)$ , and for convenience set $H_{n+1}(A)\coloneqq 1$ for any $n\times n$ matrix $A$ .

Notation 2.12.

For a given matrix $A$ , when referring to the matrix itself we use square brackets and when referring to the determinant of $A$ we use straight brackets. For instance, $A=\begin{bmatrix}1&2\\ 1&1\end{bmatrix}$ , $\det(A)=|A|=\begin{vmatrix}1&2\\ 1&1\end{vmatrix}=-1$ . To avoid confusion, we use $\operatorname{abs}(\cdot)$ for absolute value sometimes.

3 Case I

Firstly we deal with the case $t\geq s>0$ of Problem 2.4. To prove Theorem 2.6 we introduce several lemmas. For convenience, set $M_{0}\coloneqq 1$ .

Lemma 3.1.

$M_{n}\geq t\cdot M_{n-1}$ , $\forall n\in\mathbb{Z}^{+}$ .

Proof 3.2.

Suppose that maximum absolute determinant for $(n-1)\times(n-1)$ matrices is attained by a matrix $B_{(n-1)\times(n-1)}$ . Then the following inequality holds trivially

\displaystyle M_{n}\geq abs\Bigg{(}\begin{vmatrix}\begin{array}[]{c|cccc}t&0&\cdots&&0\\ \hline\cr s&&&&\\ 0&&B&&\\ \vdots&&&&\\ 0&&&&\end{array}\end{vmatrix}\Bigg{)}=t\cdot M_{n-1}.

For the next lemma, we start by writing the determinant for any matrix $A\in\mathcal{G}_{s}^{n\times n}([0,t])$ using Laplace expansion twice, firstly for the first column of the matrix $A$ and secondly for the first rows of the resulting two matrices.

	$\displaystyle\|A\|$	$\displaystyle=\footnotesize\begin{vmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1(n-1)}&a_{1n}\\ s&a_{22}&a_{23}&\cdots&a_{2(n-1)}&a_{2n}\\ 0&s&a_{33}&\cdots&a_{3(n-1)}&a_{3n}\\ 0&0&s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\ddots&\ddots&\vdots\\ 0&0&0&\cdots&s&a_{nn}\end{vmatrix}=a_{11}\begin{vmatrix}a_{22}&a_{23}&\cdots&a_{2(n-1)}&a_{2n}\\ s&a_{33}&\cdots&a_{3(n-1)}&a_{3n}\\ 0&s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&s&a_{nn}\end{vmatrix}-s\cdot\begin{vmatrix}a_{12}&a_{13}&\cdots&a_{1(n-1)}&a_{1n)}\\ s&a_{33}&\cdots&a_{3(n-1)}&a_{3n}\\ 0&s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&s&a_{nn}\end{vmatrix}=$
		$\displaystyle=(a_{11}a_{22}-s\cdot a_{12})\cdot\footnotesize\begin{vmatrix}a_{33}&\cdots&a_{3n-1}&a_{3n}\\ s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\vdots\\ 0&\cdots&s&a_{nn}\end{vmatrix}+(-1)^{1}(a_{11}a_{23}-s\cdot a_{13})\cdot\footnotesize\begin{vmatrix}\begin{array}[]{c\|cccc}s&a_{34}&a_{35}&\cdots&a_{3n}\\ \hline\cr 0&a_{44}&a_{45}&\cdots&a_{4n}\\ 0&s&a_{55}&\ddots&a_{5n}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&s&a_{nn}\end{array}\end{vmatrix}+$
		$\displaystyle+(-1)^{2}(a_{11}a_{24}-s\cdot a_{14})\cdot\footnotesize\begin{vmatrix}\begin{array}[]{cc\|ccc}s&a_{33}&a_{35}&\cdots&a_{3n}\\ 0&s&a_{45}&\cdots&a_{4n}\\ \hline\cr 0&0&a_{55}&\ddots&a_{5n}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&s&a_{nn}\end{array}\end{vmatrix}+\cdots+(-1)^{n-2}(a_{11}a_{2n}-s\cdot a_{1n})\cdot\footnotesize\begin{vmatrix}s&a_{33}&a_{34}&\cdots&a_{3(n-1)}\\ 0&s&a_{44}&\cdots&a_{4(n-1)}\\ 0&0&s&\cdots&a_{5(n-1)}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&0&s\end{vmatrix}=\hskip 142.26378pt$

	$\displaystyle{\scriptstyle=\bigg{[}(a_{11}a_{22}-s\cdot a_{12})H_{3}(A)-(a_{11}a_{23}-s\cdot a_{13})H_{4}(A)\cdot s\bigg{]}+\bigg{[}(a_{11}a_{24}-s\cdot a_{14})H_{5}(A)\cdot s^{2}-(a_{11}a_{25}-s\cdot a_{15})H_{6}(A)\cdot s^{3}\bigg{]}+\cdots}$
(3.1)		$\displaystyle{\scriptstyle\cdots+\bigg{[}(a_{11}a_{2(n-1)}-s\cdot a_{1(n-1)})H_{n}(A)\cdot s^{n-3}-(a_{11}a_{2n}-s\cdot a_{1n})H_{n+1}(A)\cdot s^{n-2}\bigg{]}}$

(The last term depends on the parity of $n$ , if $n$ is even, it is ${\scriptstyle\bigg{[}(a_{11}a_{2n}-s\cdot a_{1n})H_{n+1}(A)\cdot s^{n-2}\bigg{]}}$ .)

Now we state a new lemma which is inspired by the previous expansion.

Lemma 3.3.

For all k in $\{2,3,\dots,n-1\}$ we have the following inequality:

(3.2)

\bigg{|}(a_{11}a_{2k}-s\cdot a_{1k})\cdot H_{k+1}(A)-(a_{11}a_{2(k+1)}-s\cdot a_{1(k+1)})\cdot s\cdot H_{k+2}(A)\bigg{|}\leq t^{2}\cdot M_{n-k}+ts^{2}\cdot M_{n-k-1}

and also, for the case when $n$ is even:

(3.3)

\bigg{|}(a_{11}a_{2n}-s\cdot a_{1n})\cdot H_{n+1}(A)\bigg{|}\leq t^{2}\cdot M_{0}

Proof 3.4.

For (3.2), it is enough to show the following:

(3.4)

\smash{\displaystyle\max_{x\in[-st,t^{2}],y\in[-st^{2},s^{2}t]}}|x\cdot H_{k+1}(A)+y\cdot H_{k+2}(A)|\leq t^{2}M_{n-k}+ts^{2}M_{n-k-1}

It suffices to check four extreme cases of $x$ and $y$ , i.e,

(x,y)\in\{(-st,s^{2}t),(-st,-st^{2}),\\ (t^{2},s^{2}t),(t^{2},-st^{2})\}

Using $t\geq s>0$ , the triangle inequality, the definition of $M_{n}$ , and Lemma 3.1 we get the following inequalities for these four cases:

$(x,y)=(-st,s^{2}t)$ :

	$\displaystyle\|(-st)H_{k+1}(A)+(s^{2}t)H_{k+2}(A)\|$	$\displaystyle\leq(st)\|H_{k+1}(A)\|+(s^{2}t)\|H_{k+2}(A)\|\leq$
		$\displaystyle\leq(st)M_{n-k}+(s^{2}t)M_{n-k-1}\leq$
		$\displaystyle\leq t^{2}M_{n-k}+s^{2}tM_{n-k-1}\ \checkmark$

$(x,y)=(-st,-st^{2})$ :

	$\displaystyle\|(-st)H_{k+1}(A)+(-st^{2})H_{k+2}(A)\|$	$\displaystyle\leq(st)\|H_{k+1}(A)\|+(st^{2})\|H_{k+2}(A)\|\leq$
		$\displaystyle\leq(st)M_{n-k}+(st^{2})M_{n-k-1}=$
		$\displaystyle=(st)M_{n-k}+ts(t-s)M_{n-k-1}+ts^{2}M_{n-k-1}\leq$
		$\displaystyle\leq(st)M_{n-k}+s(t-s)M_{n-k}+ts^{2}M_{n-k-1}=$
		$\displaystyle=(2ts-s^{2})M_{n-k}+ts^{2}M_{n-k-1}\leq$
		$\displaystyle\leq t^{2}M_{n-k}+ts^{2}M_{n-k-1}\ \checkmark$

$(x,y)=(t^{2},s^{2}t)$ :

	$\displaystyle\|(t^{2})H_{k+1}(A)+(s^{2}t)H_{k+2}(A)\|$	$\displaystyle\leq t^{2}\|H_{k+1}(A)\|+s^{2}t\|H_{k+2}(A)\|\leq$
		$\displaystyle\leq t^{2}M_{n-k}+s^{2}tM_{n-k-1}\ \checkmark$

$(x,y)=(t^{2},-st^{2})$ :

|(t^{2})H_{k+1}(A)+(-st^{2})H_{k+2}(A)|=

	$\displaystyle=t^{2}\cdot\operatorname{abs}\Bigg{(}\begin{vmatrix}a_{(k+1)(k+1)}&a_{(k+1)(k+2)}&\cdots&a_{(k+1)n}\\ s&a_{(k+2)(k+2)}&\cdots&a_{(k+2)n}\\ \vdots&\ddots&\ddots&\vdots\\ 0&\cdots&s&a_{nn}\end{vmatrix}-s\cdot\begin{vmatrix}a_{(k+2)(k+2)}&a_{(k+2)(k+3)}&\cdots&a_{(k+2)n}\\ s&a_{(k+3)(k+3)}&\cdots&a_{(k+3)n}\\ \vdots&\ddots&\ddots&\vdots\\ 0&\cdots&s&a_{nn}\end{vmatrix}\Bigg{)}=$
	$\displaystyle=t^{2}\cdot\operatorname{abs}\Bigg{(}\big{(}a_{(k+1)(k+1)}-s\big{)}H_{k+2}(A)-s\cdot\begin{vmatrix}a_{(k+1)(k+2)}&a_{(k+1)(k+3)}&\cdots&a_{(k+1)n}\\ s&a_{(k+3)(k+3)}&\cdots&a_{(k+3)n}\\ \vdots&\ddots&\ddots&\vdots\\ 0&\cdots&s&a_{nn}\end{vmatrix}\Bigg{)}\leq$
	$\displaystyle\leq t^{2}\cdot\operatorname{abs}\Bigg{(}\big{(}a_{(k+1)(k+1)}-s\big{)}H_{k+2}(A)\Bigg{)}+t^{2}s\cdot\operatorname{abs}\Bigg{(}\begin{vmatrix}a_{(k+1)(k+2)}&a_{(k+1)(k+3)}&\cdots&a_{(k+1)n}\\ s&a_{(k+3)(k+3)}&\cdots&a_{(k+3)n}\\ \vdots&\ddots&\ddots&\vdots\\ 0&\cdots&s&a_{nn}\end{vmatrix}\Bigg{)}\leq$
	$\displaystyle\leq t^{2}\cdot\operatorname{abs}\Bigg{(}\big{(}a_{(k+1)(k+1)}-s\big{)}H_{k+2}(A)\Bigg{)}+t^{2}s\cdot M_{n-k-1}=$
	$\displaystyle=t^{2}\cdot\big{\|}a_{(k+1)(k+1)}-s\big{\|}\cdot\big{\|}H_{k+2}(A)\big{\|}+t^{2}s\cdot M_{n-k-1}\leq$
	$\displaystyle\leq t^{2}\cdot\big{\|}a_{(k+1)(k+1)}-s\big{\|}\cdot M_{n-k-1}+t^{2}s\cdot M_{n-k-1}\leq$
	$\displaystyle\leq t^{2}\cdot\max\{t-s,s\}\cdot M_{n-k-1}+t^{2}s\cdot M_{n-k-1}\hskip 569.05511pt$

4.1

If $t-s=\max\{t-s,s\}$ :

	$\displaystyle\|t^{2}H_{k+1}(A)-st^{2}H_{k+2}(A)\|$	$\displaystyle\leq t^{2}\cdot(t-s)\cdot M_{n-k-1}+t^{2}s\cdot M_{n-k-1}=$
		$\displaystyle=t^{3}M_{n-k-1}\leq$
		$\displaystyle\leq t^{2}M_{n-k}\leq$
		$\displaystyle\leq t^{2}M_{n-k}+ts^{2}M_{n-k-1}\ \checkmark$

4.2

If $s=\max\{t-s,s\}$ :

	$\displaystyle\|t^{2}H_{k+1}(A)-st^{2}H_{k+2}(A)\|$	$\displaystyle\leq t^{2}\cdot s\cdot M_{n-k-1}+t^{2}s\cdot M_{n-k-1}=$
		$\displaystyle=(2t^{2}s-ts^{2})M_{n-k-1}+ts^{2}M_{n-k-1}\leq$
		$\displaystyle\leq(2ts-s^{2})M_{n-k}+ts^{2}M_{n-k-1}\leq$
		$\displaystyle\leq t^{2}M_{n-k}+ts^{2}M_{n-k-1}\ \checkmark$

Hence (3.4) is done. And (3.3) is trivial.

Using the triangle inequality and Lemma 3.3 in (3.1) yields the following inequality for $M_{n}$ :

(3.5)

M_{n}\leq t^{2}M_{n-2}+ts^{2}M_{n-3}+t^{2}s^{2}M_{n-4}+ts^{4}M_{n-5}+t^{2}s^{4}M_{n-6}+ts^{6}M_{n-7}+\cdots

Note as well that we have $M_{0}=1$ , $M_{1}=t$ , $M_{2}=t^{2}$ .

Define a new sequence $(K_{n})_{n\geq 0}$ in the following way: $K_{0}=1$ , $K_{1}=t$ , $K_{2}=t^{2}$ and $K_{n}=tK_{n-1}+s^{2}K_{n-2}$ , for all $n\geq 3$ . We state two simple lemmas concerning this sequence.

Lemma 3.5.

$K_{n}=tK_{n-1}+ts^{2}K_{n-3}+ts^{4}K_{n-5}+\cdots$ for all $n\geq 1$ .

Proof 3.6.

We use induction on $n$ . For $n=1$ and $n=2$ , the equality is trivial. It is straightforward to verify that if the statement holds for $n\in\{1,2,\dots,k\}$ and then it holds for $n=k+1$ where $k\geq 2$ . By using the induction assumption:

K_{k+1}=tK_{k}+s^{2}K_{k-1}=tK_{k}+ts^{2}K_{k-2}+ts^{4}K_{k-4}+ts^{6}K_{k-6}+\cdots

Lemma 3.7.

$K_{n}=t^{2}K_{n-2}+ts^{2}K_{n-3}+t^{2}s^{2}K_{n-4}+ts^{4}K_{n-5}+\cdots$ for all $n\geq 2$ .

Proof 3.8.

For $n=2$ it is clear. Using Lemma 3.5, for any $n\geq 3$ :

	$\displaystyle K_{n}$	$\displaystyle=tK_{n-1}+s^{2}K_{n-2}=$
		$\displaystyle=t\cdot\big{(}tK_{n-2}+ts^{2}K_{n-4}+ts^{4}K_{n-6}+\cdots\big{)}+s^{2}\cdot\big{(}tK_{n-3}+ts^{2}K_{n-5}+ts^{4}K_{n-7}+\cdots\big{)}=$
		$\displaystyle=t^{2}K_{n-2}+ts^{2}K_{n-3}+t^{2}s^{2}K_{n-4}+ts^{4}K_{n-5}+\cdots$

Lemma 3.9.

$K_{n}\geq M_{n}$ for all $n\in\mathbb{N}$ .

Proof 3.10.

Notice that we already know, by Lemma 3.7 and (3.5), that

K_{0}=M_{0},\ K_{1}=M_{1},\ K_{2}=M_{2}

K_{n}=t^{2}K_{n-2}+ts^{2}K_{n-3}+t^{2}s^{2}K_{n-4}+ts^{4}K_{n-5}+\cdots

M_{n}\leq t^{2}M_{n-2}+ts^{2}M_{n-3}+t^{2}s^{2}M_{n-4}+ts^{4}M_{n-5}+\cdots

By induction, it is clear that $K_{n}\geq M_{n}$ , $\forall n\in\mathbb{N}$ .

Lemma 3.11.

$K_{n}\leq M_{n}$ for all $n\in\mathbb{N}$ .

Proof 3.12.

It suffices to give an example $A\in\mathcal{G}_{s}^{n\times n}([0,t])$ for which the absolute determinant value is equal to $K_{n}$ . Define an $n\times n$ matrix as follows:

(3.6)

U_{n}(s,t)=U_{n}\coloneqq\footnotesize\begin{bmatrix}t&0&t&0&\cdots&&\cdots\\ s&t&0&t&\cdots&&\cdots\\ 0&s&t&0&\cdots&&\cdots\\ 0&0&s&t&\ddots&&\cdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&&\vdots\\ 0&0&0&0&\ddots&t&0\\ 0&0&0&0&\cdots&s&t\end{bmatrix}_{n\times n}

i.e., $a_{ij}=t$ if $j\geq i$ and $j-i$ is even; $a_{ij}=0$ if $j>i$ and $j-i$ is odd. Note that $|U_{1}|=t=K_{1}$ , $|U_{2}|=t^{2}=K_{2}$ and by using Laplace expansion it is easy to see that

(3.7)

|U_{n}|=t\cdot|U_{n-1}|+s^{2}|U_{n-2}|

which is the same recurrence relation as for $(K_{n})_{n\geq 1}$ . Hence, for all positive integers $n$ , we have $K_{n}=|U_{n}|\leq M_{n}$ .

As a corollary of Lemma 3.9 and 3.11, $M_{n}=|U_{n}|=K_{n}$ . This completes the proof of Theorem 2.6.

QED.

In the next section we discuss what happens when $s\geq t>0$ . We are able to say something in two regimes.

4 Case II

We consider first the case when $s\gtrsim t$ , i.e., $s$ is slightly greater than $t$ .

Define permutation matrices $P_{n}^{(r)}$ and $P_{n}^{(c)}$ in the following way: Let $P_{n}^{(r)}$ be obtained by interchanging the first two rows of the $n\times n$ identity matrix and $P_{n}^{(c)}$ be obtained by interchanging the last two columns of the $n\times n$ identity matrix. And then define $U_{n}^{(r)}(s,t)=U_{n}^{(r)},\ U_{n}^{(c)}(s,t)=U_{n}^{(c)},\ U_{n}^{(rc)}(s,t)=U_{n}^{(rc)}$ in $\mathcal{G}_{s}^{n\times n}(\{0,t\})$ for $n\geq 4$ as follows:

\displaystyle P_{n}^{(r)}\cdot U_{n}^{(r)}=\footnotesize\begin{bmatrix}s&0&t&0&\cdots&&\cdots\\ t&t&0&t&\cdots&&\cdots\\ 0&s&t&0&\cdots&&\cdots\\ 0&0&s&t&\ddots&&\cdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&&\vdots\\ 0&0&0&0&\ddots&t&0\\ 0&0&0&0&\cdots&s&t\end{bmatrix},\ U_{n}^{(c)}\cdot P_{n}^{(c)}=\footnotesize\begin{bmatrix}t&0&t&0&\cdots&&\cdots\\ s&t&0&t&\cdots&&\cdots\\ 0&s&t&0&\cdots&&\cdots\\ 0&0&s&t&\ddots&&\cdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&&\vdots\\ 0&0&0&0&\ddots&t&0\\ 0&0&0&0&\cdots&t&s\end{bmatrix}

(4.1)

\text{and}\ P_{n}^{(r)}\cdot U_{n}^{(rc)}\cdot P_{n}^{(c)}=\footnotesize\begin{bmatrix}s&0&t&0&\cdots&&\cdots\\ t&t&0&t&\cdots&&\cdots\\ 0&s&t&0&\cdots&&\cdots\\ 0&0&s&t&\ddots&&\cdots\\ \vdots&\ddots&\ddots&\ddots&\ddots&&\vdots\\ 0&0&0&0&\ddots&t&0\\ 0&0&0&0&\cdots&t&s\end{bmatrix}

We can determine the relation between the determinants of these matrices and the determinant of $U_{n}$ in the following way.

Using the Laplace expansion for the first column of $P_{n}^{(r)}\cdot U_{n}^{(r)}$ we obtain

(4.2)

\operatorname{abs}(|U_{n}^{(r)}|)=\operatorname{abs}\big{(}\big{|}P_{n}^{(r)}\cdot U_{n}^{(r)}\big{|}\big{)}=s\cdot|U_{n-1}|+ts\cdot|U_{n-2}|

and similarly

(4.3)

\operatorname{abs}(|U_{n}^{(c)}|)=s\cdot|U_{n-1}|+ts\cdot|U_{n-2}|

for all $n\geq 4$ . And again using the Laplace expansion for both the first column and the last row of $P_{n}^{(r)}\cdot U_{n}^{(rc)}\cdot P_{n}^{(c)}$ we get

(4.4)

\displaystyle|U_{n}^{(rc)}|

\displaystyle=\big{|}P_{n}^{(r)}\cdot U_{n}^{(rc)}\cdot P_{n}^{(c)}\big{|}=s^{2}\cdot|U_{n-2}|+2ts^{2}\cdot|U_{n-3}|+t^{2}s^{2}\cdot|U_{n-4}|

for all $n\geq 4$ , defining $|U_{0}|\coloneqq 0$ for convenience.

Proposition 4.1.

For the statement of Theorem 2.6, $1$ is the exact upper bound for $\dfrac{s}{t}$ . More explicitly, for any $s>t$ and $n\geq 4$ , the matrix that gives the maximum absolute determinant is not $U_{n}$ .

Proof 4.2.

If $s>t$ , by (3.7) and (4.4) we have the following when $n\geq 4$ :

	$\displaystyle\|U_{n}^{(rc)}\|=s^{2}\|U_{n-2}\|+2ts^{2}\|U_{n-3}\|+t^{2}s^{2}\|U_{n-4}\|$	$\displaystyle>s^{2}\|U_{n-2}\|+ts^{2}\|U_{n-3}\|+\big{(}t^{3}\|U_{n-3}\|+t^{2}s^{2}\|U_{n-4}\|\big{)}=$
		$\displaystyle=s^{2}\|U_{n-2}\|+ts^{2}\|U_{n-3}\|+t^{2}\|U_{n-2}\|=$
(4.5)			$\displaystyle=s^{2}\|U_{n-2}\|+t\|U_{n-1}\|=\|U_{n}\|$

That means Theorem 2.6 is not valid for any $s>t$ and $n\geq 4$ .

Proposition 4.3.

For any $n\geq 4$ , $s,t>0$ consider the matrix in $\mathcal{G}_{s}^{n\times n}([0,t])$ which has the maximum absolute determinant among this set. We call it maximizing matrix. By Theorem 2.6 we know the maximizing matrix for $0<\dfrac{s}{t}\leq 1$ . Proposition 4.1 shows that the maximizing matrix changes at $\dfrac{s}{t}=1$ . We claim that the maximizing matrix changes from $U_{n}$ to $U_{n}^{(rc)}$ at $\dfrac{s}{t}=1$ .

Proof 4.4.

Suppose that for an $n\geq 4$ the maximizing matrix changes from $U_{n}$ to a matrix $R_{n}=R_{n}(s,t)\in\mathcal{G}_{s}^{n\times n}([0,t])$ at $\dfrac{s}{t}=1$ . Then the absolute value of the determinant of $R_{n}(1,1)$ must be equal to the absolute value of the determinant of $U_{n}(1,1)$ . In [9], Li Ching proved that $\operatorname{abs}(|R_{n}(1,1)|)=|U_{n}(1,1)|$ if and only if $R_{n}(1,1)\in\big{\{}U_{n}(1,1),U_{n}^{(r)}(1,1),U_{n}^{(c)}(1,1),U_{n}^{(rc)}(1,1)\big{\}}$ . Hence $R_{n}\in\big{\{}U_{n},U_{n}^{(r)},U_{n}^{(c)},U_{n}^{(rc)}\big{\}}$ .

Furthermore, we have the following inequalities for $2t>s>t$ with $n\geq 4$ :

	$\displaystyle\|U_{n-3}\|(2t-s)(s-t)s+s^{2}(s-t)^{2}\|U_{n-4}\|>0$
	$\displaystyle\Rightarrow 3ts^{2}\|U_{n-3}\|+(s^{4}+t^{2}s^{2})\|U_{n-4}\|>(s^{3}+2st^{2})\|U_{n-3}\|+2ts^{3}\|U_{n-4}\|$
	$\displaystyle\Rightarrow s^{2}\|U_{n-2}\|+2ts^{2}\|U_{n-3}\|+t^{2}s^{2}\|U_{n-4}\|>s\|U_{n-1}\|+ts\|U_{n-2}\|$
(4.6)		$\displaystyle\Rightarrow\|U_{n}^{(rc)}\|>\operatorname{abs}(\|U_{n}^{(c)}\|)=\operatorname{abs}(\|U_{n}^{(r)}\|)$

by (3.7), (4.2), (4.3) and (4.4).

So, in (4.2) and (4.4) we have shown that for $2>\dfrac{s}{t}>1$ the maximum absolute determinant is attained by $U_{n}^{(rc)}$ among these four matrices. Therefore $R_{n}=U_{n}^{(rc)}$ .

In view of the fact that $U_{n}^{(rc)}$ has become an important matrix in our investigation, we establish the recurrence relation satisfied by its determinant in the following proposition.

Proposition 4.5.

$|U_{4}^{(rc)}|=3s^{2}t^{2}$ , $|U_{5}^{(rc)}|=s^{4}t+4s^{2}t^{3}$ and $\big{(}|U_{n}^{(rc)}|\big{)}_{n\geq 4}$ satisfies the same recurrence relation as $M_{n}$ :

(4.7)

|U_{n}^{(rc)}|=t\cdot|U_{n-1}^{(rc)}|+s^{2}\cdot|U_{n-2}^{(rc)}|

for any $n\geq 6$ .

Proof 4.6.

By substituting (4.4) and using (3.7)

	$\displaystyle\|U_{n}^{(rc)}\|$	$\displaystyle=s^{2}\|U_{n-2}\|+2ts^{2}\|U_{n-3}\|+t^{2}s^{2}\|U_{n-4}\|=$
		$\displaystyle=t\big{(}s^{2}\|U_{n-3}\|+2ts^{2}\|U_{n-4}\|+t^{2}s^{2}\|U_{n-5}\|\big{)}+s^{2}\big{(}s^{2}\|U_{n-4}\|+2ts^{2}\|U_{n-5}\|+t^{2}s^{2}\|U_{n-6}\|\big{)}=$
		$\displaystyle=t\cdot\|U_{n-1}^{(rc)}\|+s^{2}\cdot\|U_{n-2}^{(rc)}\|$

Remark 4.7.

By Proposition 4.3 we know that $U_{n}^{(rc)}$ has the maximum absolute determinant value in the case $1\leq\dfrac{s}{t}\leq 1+\epsilon(n)$ for sufficiently small $\epsilon(n)>0$ depending on $n$ . So, Propositions 4.3 and 4.5 finish the proof of Theorem 2.8.

5 Case III

The third case we consider is when $s\gg t>0$ , i.e. $s$ is sufficiently larger than $t$ , depending on $n$ .

We start with an important observation which illustrates the reason why we are interested in $s\gg t$ instead of $s\geq t$ .

Observation 5.1.

The case when $s\geq t>0$ is excessively general to reach a conclusion on $M_{n}$ . More explicitly, for this case, there is no fixed matrix structure that gives the maximum absolute determinant for all values of $s>t$ .

Proof 5.2.

Consider the case when $s=100$ and $t=1$ and $n=6$ . By using MATLAB and testing all possible $2^{21}$ cases, it is not difficult to check that the maximum absolute determinant for this case is $10006000000$ and this value is attained by only two matrices:

\footnotesize A_{1}=\begin{bmatrix}1&1&0&0&0&1\\ 100&0&1&1&1&0\\ 0&100&1&1&1&0\\ 0&0&100&0&0&1\\ 0&0&0&100&0&1\\ 0&0&0&0&100&1\end{bmatrix},\ A_{2}=\begin{bmatrix}1&1&1&0&0&1\\ 100&0&0&1&1&0\\ 0&100&0&1&1&0\\ 0&0&100&1&1&0\\ 0&0&0&100&0&1\\ 0&0&0&0&100&1\end{bmatrix}

If there is a unique matrix that maximizes the absolute determinant value for all $s>t$ in $\mathcal{G}_{s}^{6\times 6}(\{0,t\})$ , then it must be the matrix $U_{6}^{(rc)}$ by Proposition 4.3. Hence $U_{6}^{(rc)}(100,1)$ must be the same with either $A_{1}$ or $A_{2}$ , but clearly it is not. So, the maximizing matrix still depends on the ratio $\dfrac{s}{t}$ .

The next theorem describes the case $s\gg t>0$ in Problem 2.4.

Theorem 5.3.

The maximum absolute determinant of an $n\times n$ upper-Hessenberg matrix with entries from the interval $[0,t]$ and subdiagonal entries fixed at $s$ such that $s\gg t>0$ (i.e. $s$ can be taken sufficiently larger than $t$ for any case) is given by $s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}$ . (We shall go on afterwards to establish a precise lower bound for $\dfrac{s}{t}$ such that this statement holds.)

Define $M_{n}\coloneqq\displaystyle\max_{A\in\mathcal{G}_{s}^{n\times n}([0,t])}\operatorname{abs}(|A|)$ again. The proof is in two parts; the first is giving an example to show that $M_{n}\geq s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}$ , and the second showing that this example has the maximum absolute determinant. We start with the first part. Define a matrix $V_{n}$ for $n\geq 2$ as follows:

(5.1)

V_{n}\coloneqq\footnotesize\begin{bmatrix}t&t&t&t&\cdots&t&0\\ s&0&0&0&\cdots&0&t\\ 0&s&0&0&\cdots&0&t\\ 0&0&s&0&\cdots&0&t\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&0&0&0&\cdots&0&t\\ 0&0&0&0&\cdots&s&t\end{bmatrix}_{n\times n}

Proposition 5.4.

$|V_{n}|=(-1)^{n}(n-1)t^{2}s^{n-2}$ for all $n\geq 2$ .

Proof 5.5.

For $n=2$ , it is clear. We use induction on $n$ , specifically, we assume that the statement is valid for $n=2,3,\dots,k-1$ and show that it then follows for $n=k$ . By using Laplace expansion for the last row, and the induction assumption:

	$\displaystyle\footnotesize\|V_{k}\|=\begin{vmatrix}t&t&t&t&\cdots&t&0\\ s&0&0&0&\cdots&0&t\\ 0&s&0&0&\cdots&0&t\\ 0&0&s&0&\cdots&0&t\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&0&0&0&\cdots&0&t\\ 0&0&0&0&\cdots&s&t\end{vmatrix}_{k\times k}$	$\displaystyle=t\cdot\footnotesize\begin{vmatrix}\begin{array}[]{cccccc\|c}t&t&t&t&\cdots&t&t\\ \hline\cr s&0&0&0&\cdots&0&0\\ 0&s&0&0&\cdots&0&0\\ 0&0&s&0&\cdots&0&0\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&0&0&0&\cdots&0&0\\ 0&0&0&0&\cdots&s&0\end{array}\end{vmatrix}_{(k-1)\times(k-1)}-s\cdot\|V_{k-1}\|=$
		$\displaystyle=t\cdot(ts^{k-2}(-1)^{k-2})-s\cdot((-1)^{k-1}(k-2)t^{2}s^{k-3})=$
		$\displaystyle=t^{2}s^{k-2}(-1)^{k}+(k-2)t^{2}s^{k-2}(-1)^{k}=$
		$\displaystyle=(-1)^{k}(k-1)t^{2}s^{k-2}$

Now, we define a new sequence of matrices $(W_{n})_{n\geq 2}$ depending on the parity of $n$ .

(5.2)

\footnotesize W_{2k+1}\coloneqq\begin{bmatrix}\makebox[0.0pt][l]{$\smash{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\overbrace{\phantom{\begin{matrix}t&t&\cdots&t\end{matrix}}}^{\text{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k}}}$}t&t&\cdots&t&\makebox[0.0pt][l]{$\smash{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\overbrace{\phantom{\begin{matrix}0&0&\cdots&0\end{matrix}}}^{\text{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k}}}$}0&0&\cdots&0&t\\ s&0&\cdots&0&t&t&\cdots&t&0\\ 0&s&\cdots&0&t&t&\cdots&t&0\\ \vdots&&\ddots&&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&s&t&t&\cdots&t&0\\ 0&0&\cdots&0&s&0&\cdots&0&t\\ 0&0&\cdots&0&0&s&\ddots&0&t\\ \vdots&&\ddots&&\ddots&&\ddots&\vdots&\vdots\\ 0&0&\cdots&&\cdots&&\cdots&s&t\end{bmatrix}\ \,\ \ \footnotesize W_{2k+2}\coloneqq\begin{bmatrix}\makebox[0.0pt][l]{$\smash{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\overbrace{\phantom{\begin{matrix}t&t&\cdots&t\end{matrix}}}^{\text{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k}}}$}t&t&\cdots&t&\makebox[0.0pt][l]{$\smash{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\overbrace{\phantom{\begin{matrix}0&0&0&\cdots&0&t\end{matrix}}}^{\text{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k+1}}}$}0&0&0&\cdots&0&t\\ s&0&\cdots&0&t&t&t&\cdots&t&0\\ 0&s&\cdots&0&t&t&t&\cdots&t&0\\ \vdots&&\ddots&&\vdots&\vdots&\ddots&\ddots&\vdots&\vdots\\ 0&0&\cdots&s&t&t&t&\cdots&t&0\\ 0&0&\cdots&0&s&0&0&\cdots&0&t\\ 0&0&\cdots&0&0&s&0&\ddots&0&t\\ \vdots&&\ddots&&\ddots&&\ddots&&\vdots&\vdots\\ \vdots&&\ddots&&\ddots&&\ddots&&\vdots&\vdots\\ 0&0&\cdots&&\cdots&&\cdots&&s&t\end{bmatrix}

Notice that $W_{2k+1}$ contains a $k\times k$ block full of $t$ ’s whereas $W_{2k+2}$ contains a $k\times(k+1)$ block; and note that if we define $W_{2k+2}$ such that it would contain a $(k+1)\times k$ block of $t$ ’s instead of a $k\times(k+1)$ block it would not change the determinant value. For later convenience we denote the alternative version $W_{2k+2}^{\prime}$

Proposition 5.6.

$|W_{n}|=\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}(-s)^{n-3}t^{3}-s|W_{n-1}|$ for all $n\geq 3$ .

Proof 5.7.

We need to show $|W_{2k+1}|=kt^{3}(-s)^{2k-2}-s|W_{2k}|$ and $|W_{2k+2}|=kt^{3}(-s)^{2k-1}-s|W_{2k+1}|$ . We are going to show only one, because the proofs in both cases are essentially identical.

Using Laplace expansion for the last row of $W_{2k+2}$ (and by iteratively – exactly $k$ times – doing it to the last row of each the resulting matrices), and by using Proposition 5.4 we get:

	$\displaystyle\|W_{2k+2}\|$	$\displaystyle=t\cdot s^{k}\cdot(-1)^{k}\cdot\|V_{k+1}\|-s\|W_{2k+1}\|=$
		$\displaystyle=t\cdot s^{k}\cdot(-1)^{k}\cdot(-1)^{k+1}kt^{2}s^{k-1}-s\|W_{2k+1}\|=$
		$\displaystyle=kt^{3}(-s)^{2k-1}-s\|W_{2k+1}\|$

Proposition 5.8.

$|W_{n}|=(-1)^{n-1}\Big{(}s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}\Big{)}$ for all $n\geq 3$ .

Proof 5.9.

Using the previous proposition, this follows straightforwardly by induction.

As a corollary of the last proposition, we have

(5.3)

M_{n}\geq\operatorname{abs}(|W_{n}|)=s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}

for all $n\geq 2$ .

So the first part of the proof is done. Next, we prove the reverse implication.

Since we are looking for the maximum absolute determinant it suffices to check $\mathcal{G}_{s}^{n\times n}(\{0,t\})$ instead of $\mathcal{G}_{s}^{n\times n}([0,t])$ .

Notice that the determinant value of any $A\in\mathcal{G}_{s}^{n\times n}(\{0,t\})$ is a polynomial in $s$ and $t$ . More explicitly, the determinant of $A$ is an element of the following set:

(-1)^{n-1}s^{n-1}t\cdot\{0,1\}+(-1)^{n-2}s^{n-2}t^{2}\cdot\Big{\{}0,1,\dots,{{n-1}\choose{1}}\Big{\}}+(-1)^{n-3}s^{n-3}t^{3}\cdot\Big{\{}0,\dots,{{n-1}\choose{2}}\Big{\}}+\cdots+t^{n}\cdot\{0,1\}

Recall that we assumed $s\gg t$ and already know (5.3). Then

	$\displaystyle M_{n}\geq s^{n-1}t+$	$\displaystyle\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}>s^{n-2}t^{2}\cdot{{n-1}\choose{1}}+s^{n-4}t^{4}\cdot{{n-1}\choose{3}}+s^{n-6}t^{6}\cdot{{n-1}\choose{5}}+\cdots=$
(5.4)			$\displaystyle=\operatorname{abs}\Big{(}(-1)^{n-2}s^{n-2}t^{2}\cdot{{n-1}\choose{1}}+(-1)^{n-4}s^{n-4}t^{4}\cdot{{n-1}\choose{3}}+\cdots\Big{)}$

This means that the sign of the determinant which gives the maximum absolute determinant cannot be $(-1)^{n-2}$ . So, its sign is $(-1)^{n-1}$ .

By (5.3) and using $s\gg t$ again,

(5.5)

M_{n}\geq s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}>s^{n-3}t^{3}\cdot{{n-1}\choose{2}}+s^{n-5}t^{5}\cdot{{n-1}\choose{4}}+\cdots

So, the maximum absolute determinant must contain the term $s^{n-1}t$ , i.e., the maximum absolute determinant is of the form $s^{n-1}t+\cdots$ .

Moreover, we also have the following

	$\displaystyle M_{n}$	$\displaystyle\geq s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}>$
(5.6)			$\displaystyle>s^{n-1}t+(-1)s^{n-2}t^{2}+s^{n-3}t^{3}\cdot{{n-1}\choose{2}}+s^{n-5}t^{5}\cdot{{n-1}\choose{4}}+\cdots$

This means that the maximum absolute determinant cannot contain the term $s^{n-2}t^{2}$ , i.e., the maximum absolute determinant is of the form $1\cdot s^{n-1}t+0\cdot s^{n-2}t^{2}+\cdots$ .

Again by $s\gg t$ and (5.3), we can state:

	$\displaystyle M_{n}$	$\displaystyle\geq s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}>$
(5.7)			$\displaystyle>s^{n-1}t+\Big{(}\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}-1\Big{)}s^{n-3}t^{3}+s^{n-5}t^{5}\cdot{{n-1}\choose{4}}+s^{n-7}t^{7}\cdot{{n-1}\choose{6}}+\cdots$

Therefore, the coefficient of $s^{n-3}t^{3}$ in the maximum absolute determinant must be at least $\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}$ .

Lemma 5.10.

For any matrix $A\in\mathcal{G}_{s}^{n\times n}(\{0,t\})$ , if the coefficient of $s^{n-2}t^{2}$ in $|A|$ is zero, then the absolute value of the coefficient of $s^{n-3}t^{3}$ is at most $\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}$ .

Proof 5.11.

Consider the determinant as a polynomial with variable $s$ . It is easy to see that for

\footnotesize A=\begin{bmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1(n-1)}&a_{1n}\\ s&a_{22}&a_{23}&\cdots&a_{2(n-1)}&a_{2n}\\ 0&s&a_{33}&\cdots&a_{3(n-1)}&a_{3n}\\ 0&0&s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\ddots&\ddots&\vdots\\ 0&0&0&\cdots&s&a_{nn}\end{bmatrix},

the determinant of $A$ can be expressed as follows:

	$\displaystyle\|A\|=$	$\displaystyle(-1)^{n-1}s^{n-1}\cdot a_{1n}+(-1)^{n-2}s^{n-2}\cdot\big{(}a_{11}a_{2n}+a_{12}a_{3n}+a_{13}a_{4n}+\cdots+a_{1(n-1)}a_{nn}\big{)}+$
(5.8)			$\displaystyle+(-1)^{n-3}s^{n-3}\cdot\Big{(}\smash{\displaystyle\sum_{1\leq i<j\leq(n-1)}}{a_{1i}a_{(i+1)j}a_{(j+1)n}}\Big{)}+\cdots$

Because the coefficient of $s^{n-2}$ in (5.11) is zero by the assumption of the lemma,

(5.9)

a_{11}a_{2n}+a_{12}a_{3n}+a_{13}a_{4n}+\cdots+a_{1(n-1)}a_{nn}=0

(5.10)

\Rightarrow a_{12}a_{3n}+a_{13}a_{4n}+\cdots+a_{1(n-2)}a_{(n-1)n}=0\ \text{and}\ a_{11}a_{2n}+a_{1(n-1)}a_{nn}=0

Notice that we can express the coefficient of $s^{n-3}$ in (5.11) as follows:

	$\displaystyle\smash{\displaystyle\sum_{1\leq i<j\leq(n-1)}}{a_{1i}a_{(i+1)j}a_{(j+1)n}}=$
	$\displaystyle=\ a_{11}\cdot a_{22}\cdot a_{3n}+a_{11}\cdot a_{23}\cdot a_{4n}+a_{11}\cdot a_{24}\cdot a_{5n}+a_{11}\cdot a_{25}\cdot a_{6n}+\cdots$	$\displaystyle+a_{11}\cdot a_{2(n-1)}\cdot a_{nn}+$
	$\displaystyle+a_{12}\cdot a_{33}\cdot a_{4n}+a_{12}\cdot a_{34}\cdot a_{4n}+a_{12}\cdot a_{35}\cdot a_{6n}+\cdots$	$\displaystyle+a_{12}\cdot a_{3(n-1)}\cdot a_{nn}+$
	$\displaystyle+a_{13}\cdot a_{44}\cdot a_{5n}+a_{13}\cdot a_{45}\cdot a_{6n}+\cdots$	$\displaystyle+a_{13}\cdot a_{4(n-1)}\cdot a_{nn}+$
	$\displaystyle+a_{14}\cdot a_{55}\cdot a_{6n}+\cdots$	$\displaystyle+a_{14}\cdot a_{5(n-1)}\cdot a_{nn}+$
	$\displaystyle\ddots\hskip 28.45274pt$	$\displaystyle\ddots\hskip 28.45274pt\vdots$
(5.11)			$\displaystyle+a_{1(n-2)}\cdot a_{(n-1)(n-1)}\cdot a_{nn}$

The first equality at (5.10) means that there are at least $n-3$ zeros among the set

\{a_{12},a_{13},\dots,a_{1(n-2)}\}\cup\{a_{3n},a_{4n},\dots,a_{(n-1)n}\}

Suppose that there are $k_{1}$ and $k_{2}$ zeros in $\{a_{12},a_{13},\dots,a_{1(n-2)}\}$ and $\{a_{3n},\dots,a_{(n-1)n}\}$ respectively. Note that we can see the expansion (5.11) as an upper triangular half of an $(n-2)\times(n-2)$ chessboard by observing that setting $a_{1i}=0$ corresponds to colouring the $i^{th}$ row (from the top) black, and setting $a_{jn}=0$ corresponds to colouring the $(n-j+1)^{st}$ column (from the right) black for $i\in\{2,3,\dots,n-2\}$ and $j\in\{3,4,\dots,(n-1)\}$ . (Notice that we do not colour for the cases $a_{11}=0$ and $a_{nn}=0$ ) (See Figure 1).

Figure 1: Case

n=9

and

a_{14}=a_{16}=a_{17}=a_{49}=a_{79}=0

The number of black squares is less than or equal to the number of zero terms in the expansion (5.11). We know that the total number of colored rows and columns is at least $(n-3)$ since $k_{1}+k_{2}\geq n-3$ . It is clear that to minimize the number of the black squares, coloured columns must be the leftmost ones and coloured rows must be lowermost ones, and $|k_{1}-k_{2}|$ must be $0$ or $1$ (depending on the parity of $n$ ). See Figure 2 for the minimizing example in the case $n=9$ .

It is easy to calculate that the minimum number of black squares is at least

(5.12)

2\cdot\dfrac{n-3}{2}\cdot\dfrac{n-1}{2}\cdot\dfrac{1}{2}=\dfrac{n^{2}-4n+3}{4}

if $n$ is odd, and

(5.13)

\dfrac{n-4}{2}\cdot\dfrac{n-2}{2}\cdot\dfrac{1}{2}+\dfrac{n-2}{2}\cdot\dfrac{n}{2}\cdot\dfrac{1}{2}=\dfrac{n^{2}-4n+4}{4}

if $n$ is even.

Hence, in the expansion (5.11), we know that at least $\dfrac{n^{2}-4n+3}{4}$ or $\dfrac{n^{2}-4n+4}{4}$ terms are zero. And the number of terms in (5.11), is ${{n-1}\choose{2}}=\dfrac{n^{2}-3n+2}{2}$ .

Figure 2: Case

n=9

and

a_{15}=a_{16}=a_{17}=a_{39}=a_{49}=a_{59}=0

Therefore, by (5.12) and (5.13) the number of nonzero terms in the (5.11) is less than or equal to

(5.14)

\dfrac{n^{2}-3n+2}{2}-\dfrac{n^{2}-4n+3}{4}=\dfrac{n^{2}-2n+1}{4}=\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}

if $n$ is odd, and

(5.15)

\dfrac{n^{2}-3n+2}{2}-\dfrac{n^{2}-4n+4}{4}=\dfrac{n^{2}-2n}{4}=\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}

if $n$ is even. As a consequence, by (5.11), (5.14) and (5.15) the absolute value of the coefficient of $s^{n-3}t^{3}$ is at most $\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}$ .

Hence, the maximum absolute determinant is

1\cdot s^{n-1}t+0\cdot s^{n-2}t^{2}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}+\cdots

by (5), the previous lemma and (5).

Now we are going to consider the entries of the matrix that makes the coefficient of $s^{n-3}t^{3}$ equal to $\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}$ .

If $n$ is odd, say $n=2k+1$ , we have a $(2k-1)\times(2k-1)$ half chessboard, and we colour $2k-2$ rows and columns in total. To make the coefficient $\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}$ , we colour exactly $(k-1)$ rows (the lowermost ones) and $(k-1)$ columns (the leftmost ones). This means we set

(5.16)

a_{1(2k-1)}=a_{1(2k-2)}=\cdots=a_{1(k+1)}=0

(5.17)

a_{3(2k+1)}=a_{4(2k+1)}=\cdots=a_{(k+1)(2k+1)}=0

Additionally all the nonzero terms in (5.11) must be $t^{3}$ , which means

(5.18)

a_{11}=a_{12}=\cdots=a_{1k}=t

(5.19)

a_{(k+2)(2k+1)}=a_{(k+3)(2k+1)}=\cdots=a_{(2k+1)(2k+1)}=t

(5.20)

a_{ij}=t\ \text{for all}\ (i,j)\in\{2,3,\dots,(k+1)\}\times\{(k+1),(k+2),\dots,(2k)\}

because there is a term $a_{1(i-1)}\cdot a_{ij}\cdot a_{(j+1)(2k+1)}$ that corresponds to a white square in the chessboard representation for each $(i,j)\in\{2,3,\dots,(k+1)\}\times\{(k+1),(k+2),\dots,(2k)\}$ .

Moreover, recall the second equation at $\eqref{eq:13}$ and we already have $a_{11}=a_{(2k+1)(2k+1)}=t$ by (5.18) and (5.19), then

(5.21)

a_{2(2k+1)}=a_{1(2k)}=0

We already know that the coefficient of $s^{n-1}$ in (5.11) is not zero, so

(5.22)

a_{1(2k+1)}=t

So far we have arrived at the following matrix structure by (5.16)-(5.22)

(5.23)

\begin{bmatrix}\makebox[0.0pt][l]{$\smash{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\overbrace{\phantom{\begin{matrix}t&t&\cdots&t\end{matrix}}}^{\text{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k}}}$}t&t&\cdots&t&\makebox[0.0pt][l]{$\smash{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\overbrace{\phantom{\begin{matrix}0&0&\cdots&0\end{matrix}}}^{\text{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k}}}$}0&0&\cdots&0&t\\ s&?&?&?&t&t&\cdots&t&0\\ 0&s&?&?&t&t&\cdots&t&0\\ \vdots&&\ddots&?&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&s&t&t&\cdots&t&0\\ 0&0&\cdots&0&s&?&?&?&t\\ 0&0&\cdots&0&0&s&?&?&t\\ \vdots&&\ddots&&\ddots&&\ddots&?&\vdots\\ 0&0&\cdots&&\cdots&&\cdots&s&t\end{bmatrix}

For the case when $n$ is even, we have the same, but according to the choice of the difference between the number of zero terms in the sets $\{a_{12},a_{13},\dots,a_{1(n-2)}\}$ and $\{a_{3n},\dots,a_{(n-1)n}\}$ , i.e. $(k_{1}-k_{2})$ , as $-1$ or $+1$ ; we are going to have $W_{2k+2}$ or $W_{2k+2}^{\prime}$ as defined at $\eqref{e:10}$ . From now on, we just consider the odd case, the even case can be done in exactly the same way.

Recall that we know that the maximum absolute determinant is

1\cdot s^{n-1}t+0\cdot s^{n-2}t^{2}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}+\cdots

Because of (5.3) and $s\gg t$ we have the following inequality,

M_{n}\geq s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}>

(5.24)

>s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}+(-1)\cdot s^{n-4}t^{4}+s^{n-5}t^{5}\cdot{{n-1}\choose{4}}+s^{n-7}t^{7}\cdot{{n-1}\choose{6}}+\cdots

Hence, the coefficient of $s^{n-4}t^{4}$ must be $0$ to have the maximum absolute determinant. Now we are going to show that this fact forces all entries with a question mark in (5.23) to be filled with $0$ .

Proposition 5.12.

Recall that we have defined $V_{n}$ in (5.1). If any of the entries of the triangular block of $0$ ’s in the upper half is $t$ instead of $0$ , then the determinant contains the term $s^{n-3}t^{3}$ .

Proof 5.13.

Consider the following permutation:

\footnotesize\begin{bmatrix}t&\cdots&&\boxed{t}&\cdots&&\cdots&t&0\\ \boxed{s}&&&\vdots&&&&&t\\ &\boxed{\ddots}&&\vdots&&&&&\\ &&\boxed{\ddots}&\vdots&&&&&\vdots\\ &&&s&\cdots&\boxed{t}&&&\\ &&&&\boxed{\ddots}&\vdots&&&\vdots\\ &&&&&s&\cdots&\cdots&\boxed{t}\\ &&&&&&\boxed{\ddots}&&\vdots\\ &&&&&&&\boxed{s}&t\end{bmatrix}

This permutation gives the term $s^{n-3}t^{3}$ , and because all the terms with $s^{n-3}$ have the same sign, $s^{n-3}t^{3}$ does not vanish.

Proposition 5.14.

Consider the matrix in (5.23), if there is $t$ in any of the entries that are filled with a question mark, then the determinant has the term $s^{n-4}t^{4}$ .

Proof 5.15.

Let $n=2k+1$ be odd, the other case can be done by the same way. Suppose that the $t$ is placed in the top-left triangular block of $?$ ’s WLOG. Then consider the determinant as follows:

\scriptsize\begin{vmatrix}\begin{array}[]{ccccc|cccc}t&t&\cdots&t&0&0&\cdots&0&t\\ s&?&?&?&t&t&\cdots&t&0\\ 0&s&?&?&t&t&\cdots&t&0\\ \vdots&&\ddots&?&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&s&t&t&\cdots&t&0\\ \hline\cr 0&0&\cdots&0&s&?&?&?&\boxed{t}\\ 0&0&\cdots&0&0&\boxed{s}&?&?&t\\ \vdots&&\ddots&&\ddots&&\boxed{\ddots}&?&\vdots\\ 0&0&\cdots&&\cdots&&\cdots&\boxed{s}&t\end{array}\end{vmatrix}

The determinant of the upper-left $(k+1)\times(k+1)$ square contains the term $t^{3}s^{k-2}$ by Proposition 5.12. And as we have boxed, there is a permutation that gives a $ts^{k-1}$ term from the bottom-right square. When we consider these two together we get the term $t^{4}s^{2k-3}$ which is exactly what we are looking for.

As a corollary, we can state that all the entries with question mark must be filled with $0$ to have the maximum absolute determinant. Therefore the matrix which has the maximum absolute determinant is the matrix $W_{2k+1}$ as we have defined at (5.2). QED.

Now we can discuss the condition $s\gg t$ . We have used this in our proof in the following ways in (5), (5.5), (5), (5) and (5.24). We can rewrite these inequalities setting $x\coloneqq\dfrac{s}{t}$ :

(5.25)			$\displaystyle x^{n-1}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}x^{n-3}>x^{n-2}\cdot{{n-1}\choose{1}}+x^{n-4}\cdot{{n-1}\choose{3}}+x^{n-6}\cdot{{n-1}\choose{5}}+\cdots$
(5.26)			$\displaystyle x^{n-1}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}x^{n-3}>x^{n-3}\cdot{{n-1}\choose{2}}+x^{n-5}\cdot{{n-1}\choose{4}}+\cdots$
(5.27)			$\displaystyle x^{n-2}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}x^{n-3}>x^{n-3}\cdot{{n-1}\choose{2}}+x^{n-5}\cdot{{n-1}\choose{4}}+\cdots$
(5.28)			$\displaystyle x^{n-3}>x^{n-5}\cdot{{n-1}\choose{4}}+x^{n-7}\cdot{{n-1}\choose{6}}+\cdots$
(5.29)			$\displaystyle x^{n-4}>x^{n-5}\cdot{{n-1}\choose{4}}+x^{n-7}\cdot{{n-1}\choose{6}}+\cdots$

Note that except in the last inequality, these allow us to take $x$ asymptotic to $n^{2}$ . However, the last one requires $n^{4}$ . Fortunately we can overcome this issue using another way to tackle the problem. Recall that we deduced (5.29) from (5.24). Before stating (5.24), we found that the maximum absolute determinant has the form $1\cdot s^{n-1}t+0\cdot s^{n-2}t^{2}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}+\cdots$ and the matrix with this determinant has the form (5.23)

Lemma 5.16.

Let

A=\scriptsize\begin{bmatrix}t&t&\cdots&t&0&0&\cdots&0&t\\ s&a_{22}&\cdots&a_{2k}&t&t&\cdots&t&0\\ 0&s&\ddots&\vdots&t&t&\cdots&t&0\\ \vdots&&\ddots&a_{kk}&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&s&t&t&\cdots&t&0\\ 0&0&\cdots&0&s&a_{(k+2)(k+2)}&\cdots&a_{(k+2)(2k)}&t\\ 0&0&\cdots&0&0&s&\ddots&\vdots&t\\ \vdots&&\ddots&&\ddots&\ddots&\ddots&a_{(2k)(2k)}&\vdots\\ 0&0&\cdots&&\cdots&\cdots&0&s&t\end{bmatrix},

where $A\in\mathcal{G}_{s}^{n\times n}(\{0,t\})$ . And let

(5.30)

\operatorname{abs}(|A|)=1\cdot s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}-b_{4}\cdot s^{n-4}t^{4}+b_{5}\cdot s^{n-5}t^{5}-b_{6}\cdot s^{n-6}t^{6}+\cdots

Then, $b_{m}\cdot n\geq b_{m+1}$ for all $m\in\{4,5,\dots,n-1\}$ .

Proof. Recall that in the permutation definition, if we consider the determinant as a function of $s$ , the absolute value of the coefficient of $s^{n-l}$ is:

(5.31)

\smash{\displaystyle\sum_{1\leq i_{1}<\cdots<i_{l-1}\leq(n-1)}}{a_{1i_{1}}a_{(i_{1}+1)i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{l-1}+1)n}}

Then

(5.32)

b_{m}\cdot t^{m}=\smash{\displaystyle\sum_{1\leq i_{1}<\cdots<i_{m-1}\leq(n-1)}}{a_{1i_{1}}a_{(i_{1}+1)i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m-1}+1)n}}

and

(5.33)

b_{m+1}\cdot t^{m+1}=\smash{\displaystyle\sum_{1\leq i_{1}<\cdots<i_{m}\leq(n-1)}}{a_{1i_{1}}a_{(i_{1}+1)i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m}+1)n}}

Clearly some of the terms are going to vanish such as the ones starting with $a_{1(k+1)}$ because $a_{1(k+1)}$ is already determined as $0$ . Now we are going to define a function from non-vanishing terms in (5.33) to non-vanishing terms in (5.32). (From now on we consider them not as numbers, but as sequences of $a_{ij}$ ’s) Define the function

\phi:B_{m+1}\coloneqq\Big{\{}a_{1i_{1}}a_{(i_{1}+1)i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m}+1)n}\neq 0\big{|}1\leq i_{1}<\cdots<i_{m}\leq(n-1)\Big{\}}\rightarrow

\leavevmode\nobreak\ \ \hskip 71.13188pt\rightarrow B_{m}\coloneqq\Big{\{}a_{1i_{1}}a_{(i_{1}+1)i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m-1}+1)n}\neq 0\big{|}1\leq i_{1}<\cdots<i_{m-1}\leq(n-1)\Big{\}}

as follows:

•

If $i_{2}\leq k(=\frac{n-1}{2})$ , we have $a_{1i_{2}}\neq 0$ ,

\phi\big{(}a_{1i_{1}}a_{(i_{1}+1)i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m}+1)n}\big{)}\coloneqq a_{1i_{2}}a_{(i_{2}+1)i_{3}}a_{(i_{3}+1)i_{4}}\cdots a_{(i_{m}+1)n}

•

If $i_{2}\geq k+1$ , then $i_{m-1}\geq i_{2}\geq k+1$ , we have $a_{(i_{m-1}+1)n}\neq 0$ ,

\phi\big{(}a_{1i_{1}}a_{(i_{1}+1)i_{2}}\cdots a_{(i_{m-1}+1)i_{m}}a_{(i_{m}+1)n}\big{)}\coloneqq a_{1i_{1}}a_{(i_{1}+1)i_{2}}\cdots a_{(i_{m-2}+1)i_{m-1}}a_{(i_{m-1}+1)n}

We are going to show that the preimage of any element in the range has cardinality less than or equal to $n$ .

Consider the preimage of an arbitrary element in the range of $\phi$ ,

\phi^{-1}\Bigg{[}\phi\big{(}a_{1i_{1}}a_{(i_{1}+1)i_{2}}\cdots a_{(i_{m-1}+1)i_{m}}a_{(i_{m}+1)n}\big{)}\Bigg{]}

Define a set $P_{1}\coloneqq\emptyset$ if $i_{2}\geq k+1$ , otherwise $P_{1}\coloneqq$
$\coloneqq\Big{\{}a_{11}a_{2i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m-1}+1)i_{m}}a_{(i_{m}+1)n},a_{12}a_{3i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m-1}+1)i_{m}}a_{(i_{m}+1)n},\dots$
$\dots,a_{1(i_{2}-1)}a_{i_{2}i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m-1}+1)i_{m}}a_{(i_{m}+1)n}\Big{\}}$

Similarly define $P_{2}\coloneqq\emptyset$ if $i_{m-1}\leq k$ , otherwise $P_{2}\coloneqq$
$\coloneqq\Big{\{}a_{1i_{1}}a_{(i_{1}+1)i_{2}}\cdots a_{(i_{m-2}+1)i_{m-1}}a_{(i_{m-1}+1)(i_{m-1}+1)}a_{(i_{m-1}+2)n},a_{1i_{1}}a_{(i_{1}+1)i_{2}}\cdots a_{(i_{m-2}+1)i_{m-1}}a_{(i_{m-1}+1)(i_{m-1}+2)}a_{(i_{m-1}+3)n},\dots$

$\dots,a_{1i_{1}}a_{(i_{1}+1)i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m-2}+1)i_{m-1}}a_{(i_{m-1}+1)(n-1)}a_{nn}\Big{\}}$

It is not difficult to see that

\phi^{-1}\Bigg{[}\phi\big{(}a_{1i_{1}}a_{(i_{1}+1)i_{2}}\cdots a_{(i_{m-1}+1)i_{m}}a_{(i_{m}+1)n}\big{)}\Bigg{]}\subseteq P_{1}\cup P_{2}

and for the cardinality of $P_{1}\cup P_{2}$ we have

|P_{1}\cup P_{2}|\leq|P_{1}|+|P_{2}|\leq(k-1)+(k-1)\leq n

Therefore, we get that the preimage of any element in $B_{m}$ has cardinality less than or equal to $n$ and this means $|B_{m}|\cdot n\geq|B_{m+1}|$ .

Note that:

b_{m}\cdot t^{m}=\smash{\displaystyle\sum_{1\leq i_{1}<\cdots<i_{m-1}\leq(n-1)}}{a_{1i_{1}}a_{(i_{1}+1)i_{2}}a_{(i_{2}+1)i_{3}}\cdots a_{(i_{m-1}+1)n}}=t^{m}\cdot|B_{m}|\Rightarrow b_{m}=|B_{m}|

and similarly

b_{m+1}=|B_{m+1}|

Hence

\hskip 159.3356ptb_{m+1}=|B_{m+1}|\leq n\cdot|B_{m}|=n\cdot b_{m}\hskip 153.6447pt\leavevmode\nobreak\ \vbox{\hrule\hbox{\vrule height=5.59721pt\hskip 3.44444pt\vrule}\hrule}

As a corollary of Lemma 5.16, we can write the following inequality for (5.30) if $\dfrac{s}{t}\geq n$ :

	$\displaystyle\operatorname{abs}(\|A\|)$	$\displaystyle=1\cdot s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}-b_{4}\cdot s^{n-4}t^{4}+b_{5}\cdot s^{n-5}t^{5}-b_{6}\cdot s^{n-6}t^{6}+\cdots=$
		$\displaystyle=s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}-s^{n-5}t^{4}\big{(}s\cdot b_{4}-t\cdot b_{5}\big{)}-s^{n-7}t^{6}\big{(}s\cdot b_{6}-t\cdot b_{7}\big{)}+\cdots\leq$
		$\displaystyle\leq s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}-s^{n-5}t^{4}\big{(}s\cdot b_{4}-t\cdot n\cdot b_{4}\big{)}-s^{n-7}t^{6}\big{(}s\cdot b_{6}-t\cdot n\cdot b_{6}\big{)}+\cdots=$
		$\displaystyle=s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}-s^{n-5}t^{5}b_{4}\big{(}\dfrac{s}{t}-n\big{)}-s^{n-7}t^{7}b_{6}\big{(}\dfrac{s}{t}-n\big{)}+\cdots\leq$
(5.34)			$\displaystyle\leq s^{n-1}t+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}s^{n-3}t^{3}$

So having $\dfrac{s}{t}\geq n$ is sufficient for the last case, namely (5.29) is not a requirement anymore if $\dfrac{s}{t}\geq n$ . Then there are four inequalities left that we still need to deal with: (5.25)-(5.28).

Lemma 5.17.

If $\dfrac{s}{t}=x>\dfrac{1}{\cosh^{-1}(2)}\cdot n^{2}$ these inequalities hold for $n\geq 2$ .

Proof 5.18.

Start with the first one, (5.25), we know that

\dfrac{3}{2}\cdot n<\dfrac{1}{\cosh^{-1}(2)}\cdot n^{2}<x\ ,

then

	$\displaystyle x^{n-2}{{n-1}\choose{1}}+x^{n-4}{{n-1}\choose{3}}+x^{n-6}{{n-1}\choose{5}}+\cdots\$	$\displaystyle<\ x^{n-2}\cdot n+x^{n-4}\cdot\dfrac{n^{3}}{3!}+x^{n-6}\cdot\dfrac{n^{5}}{5!}+\cdots\ <$
		$\displaystyle<\ \dfrac{2}{3}\cdot x^{n-1}+\big{(}\dfrac{2}{3}\big{)}^{3}\cdot\dfrac{x^{n-1}}{3!}+\big{(}\dfrac{2}{3}\big{)}^{5}\cdot\dfrac{x^{n-1}}{5!}+\cdots\ <$
		$\displaystyle<\ \dfrac{2}{3}\cdot x^{n-1}\cdot\big{(}1+\dfrac{1}{3!}+\dfrac{1}{5!}+\cdots\big{)}\ <$
		$\displaystyle<\ \dfrac{2}{3}\cdot x^{n-1}\cdot\sinh(1)\ <\ x^{n-1}\ <$
		$\displaystyle<\ x^{n-1}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}x^{n-3}\ \checkmark$

For the second one (5.26), use the first inequality (5.25),

	$\displaystyle x^{n-1}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}x^{n-3}$	$\displaystyle>x^{n-2}{{n-1}\choose{1}}+x^{n-4}{{n-1}\choose{3}}+x^{n-6}{{n-1}\choose{5}}+\cdots\ >$
		$\displaystyle>\ x^{n-3}\cdot n\cdot{{n-1}\choose{1}}+x^{n-5}\cdot n\cdot{{n-1}\choose{3}}+\cdots>$
		$\displaystyle>x^{n-3}\cdot{{n-1}\choose{2}}+x^{n-5}\cdot{{n-1}\choose{4}}+\cdots\ \checkmark$

For the third case (5.27),

	$\displaystyle x^{n-3}\cdot{{n-1}\choose{2}}+x^{n-5}\cdot{{n-1}\choose{4}}+\cdots\ <\ x^{n-3}\cdot\dfrac{n^{2}}{2!}+x^{n-5}\cdot\dfrac{n^{4}}{4!}+x^{n-7}\cdot\dfrac{n^{6}}{6!}+\cdots\$	$\displaystyle<$
	$\displaystyle<\ x^{n-2}\cdot\dfrac{(\cosh^{-1}(2))^{1}}{2!}+x^{n-3}\cdot\dfrac{(\cosh^{-1}(2))^{2}}{4!}+x^{n-4}\cdot\dfrac{(\cosh^{-1}(2))^{3}}{6!}+\cdots\$	$\displaystyle<$
	$\displaystyle<\ x^{n-2}\cdot\dfrac{(\cosh^{-1}(2))^{2}}{2!}+x^{n-3}\cdot\dfrac{(\cosh^{-1}(2))^{4}}{4!}+x^{n-4}\cdot\dfrac{(\cosh^{-1}(2))^{6}}{6!}+\cdots\$	$\displaystyle<$
	$\displaystyle<\ x^{n-2}\cdot\dfrac{(\cosh^{-1}(2))^{2}}{2!}+x^{n-2}\cdot\dfrac{(\cosh^{-1}(2))^{4}}{4!}+x^{n-2}\cdot\dfrac{(\cosh^{-1}(2))^{6}}{6!}+\cdots\$	$\displaystyle<$
	$\displaystyle<\ x^{n-2}\cdot\bigg{[}\cosh\big{(}\cosh^{-1}(2)\big{)}-1\bigg{]}\ =\ x^{n-2}\ <\ x^{n-2}+\Big{\lfloor}\dfrac{n}{2}\Big{\rfloor}\Big{\lfloor}\dfrac{n-1}{2}\Big{\rfloor}x^{n-3}\$	$\displaystyle\checkmark$

And for the last inequality (5.28),

	$\displaystyle x^{n-5}\cdot{{n-1}\choose{4}}+x^{n-7}\cdot{{n-1}\choose{6}}+\cdots\$	$\displaystyle<\ x^{n-5}\cdot\dfrac{n^{4}}{4!}+x^{n-7}\cdot\dfrac{n^{6}}{6!}+\cdots\ <$
		$\displaystyle<x^{n-3}\cdot\dfrac{(\cosh^{-1}(2))^{2}}{4!}+x^{n-4}\cdot\dfrac{(\cosh^{-1}(2))^{3}}{6!}+\cdots\ <$
		$\displaystyle<x^{n-3}\cdot\dfrac{(\cosh^{-1}(2))^{4}}{4!}+x^{n-4}\cdot\dfrac{(\cosh^{-1}(2))^{6}}{6!}+\cdots\ <$
		$\displaystyle<x^{n-3}\cdot\dfrac{(\cosh^{-1}(2))^{4}}{4!}+x^{n-3}\cdot\dfrac{(\cosh^{-1}(2))^{6}}{6!}+\cdots\ <$
		$\displaystyle<x^{n-3}\cdot\bigg{[}\cosh\big{(}\cosh^{-1}(2)\big{)}-1\bigg{]}\ =\ x^{n-3}\ \checkmark$

Remark 5.19.

For simplicity we can write $\dfrac{4}{5}$ instead of $\dfrac{1}{\cosh^{-1}(2)}$ since we are not interested in the strict lower bound. Thus Theorem 5.3 and Lemma 5.17 finish the proof of Theorem 2.9.

Remark 5.20.

The lower bound in Theorem 2.9 is not sharp, but it is clear from the inequality (5.28) that it is asymptotic to $n^{2}$ for our proof to hold.

6 Concluding Remarks

We found the maximum absolute determinants (and the matrices giving the corresponding values) for the cases $\dfrac{s}{t}>\dfrac{4}{5}\cdot n^{2}$ (Theorem 2.9) and $0\leq\dfrac{s}{t}\leq 1$ (Theorem 2.6); in addition we already know the case $\dfrac{s}{t}\leq 0$ (Theorem 2.5). Furthermore we showed that $1$ is the exact upper bound of $\dfrac{s}{t}$ for Theorem 2.6 (Proposition 4.1), and found the first maximizing matrix after $\dfrac{s}{t}=1$ (Proposition 4.3) with the recurrence relation satisfied by its absolute determinant value (Proposition 4.5). Nevertheless, for the most part the problem as to what happens if $1<\dfrac{s}{t}<\dfrac{4}{5}\cdot n^{2}$ still remains open. Note that as $\dfrac{s}{t}$ goes to $1$ from $\dfrac{4}{5}\cdot n^{2}$ , the matrix which gives the maximum absolute determinant changes from having a localized to a much more uniform structure. In view of these observations, further investigations might be based on the following questions:

1.

Which matrices maximize the absolute determinant as $\dfrac{s}{t}$ goes to $1$ from $n^{2}$ , in other words, what are the transition forms?
2.

It is reasonable to work on the case $s=2$ and $t=1$ as a first step to understanding the transition form. Is $U_{n}^{(rc)}$ the maximizing matrix in this case when $n\geq 4$ ?
3.

How many times do transitions occur depending on the size of the matrices?
4.

We know that for $n\geq 4$ the first transition occurs at $\dfrac{s}{t}=1$ from $U_{n}$ to $U_{n}^{(rc)}$ . When does the second transition occur, in other words what is the maximum possible value of $\epsilon(n)$ in Remark 4.7?
5.

What should be the precise lower bound in Theorem 5.3? Is it asymptotic to $n^{2}$ ?
6.

When do other transitions occur?
7.

Note that the number of $t$ ’s in the matrices $U_{n}$ (3.6), $U_{n}^{(rc)}$ (4.1) and $W_{n}$ (5.2) are equal. Is it true that for any fixed $n$ , all maximizing matrices have the same number of $t$ ’s?
8.

Moreover, there is no alternating sign among the nonzero permutations in the determinants for any of these three matrices. Is this condition valid for all maximizing matrices?

Acknowledgements

We thank Professor N. J. Higham for drawing our attention to questions concerning Bohemian Matrices. The work reported here was carried out as part of an undergraduate summer research project by Mr Ahmet Abdullah Keleş at the University of Bristol, June–July 2019. Mr Keleş is grateful for financial support and the hospitality of the School of Mathematics at the University of Bristol during his visit. JPK was supported by a Royal Society Wolfson Research Merit Award, EPSRC Programme Grant EP/K034383/1 LMF: $L$ -Functions and Modular Forms, and by ERC Advanced Grant 740900 (LogCorRM).

References

[1] Sylvester J. J. “Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers.” Philos Mag. 1867; 34: 461-475.
[2] Hadamard J. “Resolution d’une question relative aux determinants.” Bull Sci Math. 1893; 17: 240– 246.
[3] Bressoud, D. Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture. Cambridge, England: Cambridge University Press, 1999.
[4] Vu V. “Random discrete matrices.” Bolyai Soc Math Stud 17 (2008), 257-280.
[5] Chan, E. Y. S., Corless. R. M., Gonzalez-Vega, L., Sendra, J. R., Sendra, J. and Thornton, S.E. “Bohemian Upper Hessenberg Matrices.” arXiv:1809.10653, September 2018.
[6] Thornton, Steven E. “Algorithms for Bohemian Matrices” (2019). Electronic Thesis and Dissertation Repository. 6069. https://ir.lib.uwo.ca/etd/6069
[7] Thornton, Steven E. “The Characteristic Polynomial Database.” published electronically at http://bohemianmatrices.com/cpdb, 08.07.2019.
[8] Fasi, Massimiliano and Negri Porzio, Gian Maria. “Determinants of Normalized Bohemian Upper Hessemberg Matrices.” MIMS EPrint 2019.7, Manchester Institute for Mathematical Sciences, The University of Manchester, UK, 2019. To appear in Electron. J. Linear Algebra.
[9] Ching L. “The maximum determinant of an $n\times n$ lower Hessenberg $(0,1)$ matrix.” Linear Algebra and its Applications, 183 (1993): 147-153.
[10] Harary, F. “The determinant of the adjacency matrix of a graph.” SIAM Rev., 4 (1962): 202-210.

	$\displaystyle\|A\|$	$\displaystyle=\footnotesize\begin{vmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1(n-1)}&a_{1n}\\ s&a_{22}&a_{23}&\cdots&a_{2(n-1)}&a_{2n}\\ 0&s&a_{33}&\cdots&a_{3(n-1)}&a_{3n}\\ 0&0&s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\ddots&\ddots&\vdots\\ 0&0&0&\cdots&s&a_{nn}\end{vmatrix}=a_{11}\begin{vmatrix}a_{22}&a_{23}&\cdots&a_{2(n-1)}&a_{2n}\\ s&a_{33}&\cdots&a_{3(n-1)}&a_{3n}\\ 0&s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&s&a_{nn}\end{vmatrix}-s\cdot\begin{vmatrix}a_{12}&a_{13}&\cdots&a_{1(n-1)}&a_{1n)}\\ s&a_{33}&\cdots&a_{3(n-1)}&a_{3n}\\ 0&s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&s&a_{nn}\end{vmatrix}=$
		$\displaystyle=(a_{11}a_{22}-s\cdot a_{12})\cdot\footnotesize\begin{vmatrix}a_{33}&\cdots&a_{3n-1}&a_{3n}\\ s&\ddots&a_{4(n-1)}&a_{4n}\\ \vdots&\ddots&\ddots&\vdots\\ 0&\cdots&s&a_{nn}\end{vmatrix}+(-1)^{1}(a_{11}a_{23}-s\cdot a_{13})\cdot\footnotesize\begin{vmatrix}\begin{array}[]{c\|cccc}s&a_{34}&a_{35}&\cdots&a_{3n}\\ \hline\cr 0&a_{44}&a_{45}&\cdots&a_{4n}\\ 0&s&a_{55}&\ddots&a_{5n}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&s&a_{nn}\end{array}\end{vmatrix}+$
		$\displaystyle+(-1)^{2}(a_{11}a_{24}-s\cdot a_{14})\cdot\footnotesize\begin{vmatrix}\begin{array}[]{cc\|ccc}s&a_{33}&a_{35}&\cdots&a_{3n}\\ 0&s&a_{45}&\cdots&a_{4n}\\ \hline\cr 0&0&a_{55}&\ddots&a_{5n}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&s&a_{nn}\end{array}\end{vmatrix}+\cdots+(-1)^{n-2}(a_{11}a_{2n}-s\cdot a_{1n})\cdot\footnotesize\begin{vmatrix}s&a_{33}&a_{34}&\cdots&a_{3(n-1)}\\ 0&s&a_{44}&\cdots&a_{4(n-1)}\\ 0&0&s&\cdots&a_{5(n-1)}\\ \vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&\cdots&0&s\end{vmatrix}=\hskip 142.26378pt$

	$\displaystyle\|U_{n}^{(rc)}\|=s^{2}\|U_{n-2}\|+2ts^{2}\|U_{n-3}\|+t^{2}s^{2}\|U_{n-4}\|$	$\displaystyle>s^{2}\|U_{n-2}\|+ts^{2}\|U_{n-3}\|+\big{(}t^{3}\|U_{n-3}\|+t^{2}s^{2}\|U_{n-4}\|\big{)}=$
		$\displaystyle=s^{2}\|U_{n-2}\|+ts^{2}\|U_{n-3}\|+t^{2}\|U_{n-2}\|=$
(4.5)			$\displaystyle=s^{2}\|U_{n-2}\|+t\|U_{n-1}\|=\|U_{n}\|$

	$\displaystyle\|U_{n-3}\|(2t-s)(s-t)s+s^{2}(s-t)^{2}\|U_{n-4}\|>0$
	$\displaystyle\Rightarrow 3ts^{2}\|U_{n-3}\|+(s^{4}+t^{2}s^{2})\|U_{n-4}\|>(s^{3}+2st^{2})\|U_{n-3}\|+2ts^{3}\|U_{n-4}\|$
	$\displaystyle\Rightarrow s^{2}\|U_{n-2}\|+2ts^{2}\|U_{n-3}\|+t^{2}s^{2}\|U_{n-4}\|>s\|U_{n-1}\|+ts\|U_{n-2}\|$
(4.6)		$\displaystyle\Rightarrow\|U_{n}^{(rc)}\|>\operatorname{abs}(\|U_{n}^{(c)}\|)=\operatorname{abs}(\|U_{n}^{(r)}\|)$

	$\displaystyle\|U_{n}^{(rc)}\|$	$\displaystyle=s^{2}\|U_{n-2}\|+2ts^{2}\|U_{n-3}\|+t^{2}s^{2}\|U_{n-4}\|=$
		$\displaystyle=t\big{(}s^{2}\|U_{n-3}\|+2ts^{2}\|U_{n-4}\|+t^{2}s^{2}\|U_{n-5}\|\big{)}+s^{2}\big{(}s^{2}\|U_{n-4}\|+2ts^{2}\|U_{n-5}\|+t^{2}s^{2}\|U_{n-6}\|\big{)}=$
		$\displaystyle=t\cdot\|U_{n-1}^{(rc)}\|+s^{2}\cdot\|U_{n-2}^{(rc)}\|$

	$\displaystyle\|W_{2k+2}\|$	$\displaystyle=t\cdot s^{k}\cdot(-1)^{k}\cdot\|V_{k+1}\|-s\|W_{2k+1}\|=$
		$\displaystyle=t\cdot s^{k}\cdot(-1)^{k}\cdot(-1)^{k+1}kt^{2}s^{k-1}-s\|W_{2k+1}\|=$
		$\displaystyle=kt^{3}(-s)^{2k-1}-s\|W_{2k+1}\|$