Single machine Pareto scheduling with positional deadlines and agreeable release and processing times

1.   Introduction

Let $\mathbb{M}_n$ be the set of $n\times n$ complex matrices. $\mathbb{M}_n(\mathbb{M}_k)$ is the set of $n\times n$ block matrices with each block in $\mathbb{M}_k$. For $A \in \mathbb{M}_n$, the conjugate transpose of $A$ is denoted by $A^*.$ When $A$ is Hermitian, we denote the eigenvalues of $A$ in nonincreasing order $\lambda_1(A) \geq \lambda_2(A) \geq... \geq \lambda_n(A)$; see ^[2,7,8,9]. The singular values of $A$, denoted by $s_1(A), s_2(A), ..., s_n(A),$ are the eigenvalues of the positive semi-definite matrix $|A| = (A^*A)^{1/2}$, arranged in nonincreasing order and repeated according to multiplicity as $s_1(A) \geq s_2(A) \geq... \geq s_n(A).$ If $A\in \mathbb{M}_n$ is positive semi-definite (definite), then we write $A \geq 0\; (A > 0)$. Every $A\in \mathbb{M}_n$ admits what is called the cartesian decomposition $A = {{{\rm{Re\, }}}} A+i{{{\rm{Im\, }}}} A,$ where ${{{\rm{Re\, }}}} A = \frac{A+A^*}{2}, \ {{{\rm{Im\, }}}} A = \frac{A-A^*}{2}.$ A matrix $A\in \mathbb{M}_n$ is called accretive if ${{{\rm{Re\, }}}} A$ is positive definite. Recall that a norm $||\cdot||$ on $\mathbb{M}_n$ is unitarily invariant if $||UAV|| = ||A||$ for any $A\in \mathbb{M}_n$ and unitary matrices $U, V\in \mathbb{M}_n$. The Hilbert-Schmidt norm is defined as $||A||_2^2 = {{{\rm{tr}}}}(A^*A)$.

For $A, B > 0$ and $t\in [0, 1]$, the weighted geometric mean of $A$ and $B$ is defined as follows

When $t = \frac{1}{2}$, $A\sharp_{\frac{1}{2}} B$ is called the geometric mean of $A$ and $B$, which is often denoted by $A\sharp B$. It is known that the notion of the (weighted) geometric mean could be extended to cover all positive semi-definite matrices; see [3, Chapter 4].

Let $A, B, X\in \mathbb{M}_n$. For $2\times 2$ block matrix $M$ in the form

with each block in $\mathbb{M}_{n},$ its partial transpose of $M$ is defined by

If $M$ and $M^\tau \geq0$, then we say it is positive partial transpose (PPT). We extend the notion to accretive matrices. If

and

are both accretive, then we say that $M$ is APT (i.e., accretive partial transpose). It is easy to see that the class of APT matrices includes the class of PPT matrices; see ^[6,10,13].

Recently, many results involving the off-diagonal block of a PPT matrix and its diagonal blocks were presented; see ^[5,11,12]. In 2023, Alakhrass ^[1] presented the following two results on $2\times2$ block PPT matrices.

Theorem 1.1 (^[1], Theorem 3.1). Let $\left(\begin{array}{cc} A & X \\ X^{*} & B\\ \end{array} \right)$ be PPT and let $X = U|X|$ be the polar decomposition of $X$, then

Theorem 1.2 (^[1], Theorem 3.2). Let $\left(\begin{array}{cc} A & X \\ X^{*} & B\\ \end{array} \right)$ be PPT, then for $t\in [0, 1],$

and

By Theorem 1.1 and the fact $s_{i+j-1}(XY)\leq s_i(X)s_j(Y)\; (i+j\leq n+1)$, the author obtained the following corollary.

Corollary 1.3 (^[1], Corollary 3.5). Let $\left(\begin{array}{cc} A & X \\ X^{*} & B\\ \end{array} \right)$ be PPT, then for $t\in [0, 1],$

Consequently,

A careful examination of Alakhrass' proof in Corollary 1.3 actually revealed an error. The right results are $s_{i+j-1}(X)\leq s_i(A\sharp_t B)^{\frac{1}{2}}s_j((A\sharp_{1-t} B)^{\frac{1}{2}})$ and $s_{2j-1}(X)\leq s_j((A\sharp_t B)^{\frac{1}{2}})$$s_j((A\sharp_{1-t} B)^{\frac{1}{2}}).$ Thus, in this note, we will give a correct proof of Corollary 1.3 and extend the above inequalities to the class of $2\times2$ block APT matrices. At the same time, some relevant results will be obtained.

2.   Main results

Before presenting and proving our results, we need the following several lemmas of the weighted geometric mean of two positive matrices.

Lemma 2.1. [3, Chapter 4] Let $X, Y\in \mathbb{M}_{n}$ be positive definite, then

$1)$ $X\sharp Y = \max\left\{Z:Z = Z^*, \left(\begin{array}{cc} X & Z \\ Z & Y\\ \end{array} \right)\geq 0\right\}.$

$2)$ $X\sharp Y = X^{\frac{1}{2}}UY^{\frac{1}{2}}$ for some unitary matrix $U$.

Lemma 2.2. [4, Theorem 3] Let $X, Y\in \mathbb{M}_{n}$ be positive definite, then for every unitarily invariant norm,

Now, we give a lemma that will play an important role in the later proofs.

Lemma 2.3. Let $M = \left(\begin{array}{cc} A & X \\ Y^{*} & B\\ \end{array} \right)\in \mathbb{M}_{2n}$ be APT, then for $t\in [0, 1]$,

is PPT.

Proof: Since $M$ is APT, we have that

is PPT.

Therefore, ${{{\rm{Re\, }}}} M \geq 0$ and ${{{\rm{Re\, }}}} M^{\tau} \geq 0$.

By the Schur complement theorem, we have

and

Compute

Thus,

By utilizing $({{{\rm{Re\, }}}} B\sharp_t {{{\rm{Re\, }}}} A) = {{{\rm{Re\, }}}} A\sharp_{1-t} {{{\rm{Re\, }}}} B$, we have

Similarly, we have

This completes the proof.

First, we give the correct proof of Corollary 1.3.

Proof: By Theorem 1.1, there exists a unitary matrix $U\in \mathbb{M}_{n}$ such that $|X|\leq (A\sharp_t B)\sharp (U^*$$(A\sharp_{1-t} B)U).$ Moreover, by Lemma 2.1, we have $(A\sharp_t B)\sharp (U^*(A\sharp_{1-t} B)U) = (A\sharp_t B)^{\frac{1}{2}}V(U^*$$(A\sharp_{1-t} B)^{\frac{1}{2}}U).$ Now, by $s_{i+j-1}(AB)\leq s_i(A)s_j(B)$, we have

which completes the proof.

Next, we generalize Theorem 1.1 to the class of APT matrices.

Theorem 2.4. Let $M = \left(\begin{array}{cc} A & X \\ Y^{*} & B\\ \end{array} \right)$ be APT, then

where $U\in \mathbb{M}_{n}$ is any unitary matrix such that $\frac{X+Y}{2} = U\left|\frac{X+Y}{2}\right|$.

Proof: Since $M$ is an APT matrix, we know that

is PPT.

Let $W$ be a unitary matrix defined as $W = \left(\begin{array}{cc} I & 0\\ 0 & U\\ \end{array} \right)$. Thus,

By Lemma 2.1, we have

Remark 1. When $M = \left(\begin{array}{cc} A & X \\ Y^{*} & B\\ \end{array} \right)$ is PPT in Theorem 2.4, our result is Theorem 1.1. Thus, our result is a generalization of Theorem 1.1.

Using Theorem 2.4 and Lemma 2.2, we have the following.

Corollary 2.5. Let $M = \left(\begin{array}{cc} A & X \\ Y^{*} & B\\ \end{array} \right)$ be APT and let $t\in[0, 1]$, then for every unitarily invariant norm $|| \cdot ||$ and some unitary matrix $U\in \mathbb{M}_n,$

Proof: The first inequality follows from Theorem 2.4. The third one is by the triangle inequality. The other conclusions hold by Lemma 2.2.

In particular, when $t = \frac{1}{2},$ we have the following result.

Corollary 2.6. Let $M = \left(\begin{array}{cc} A & X \\ Y^{*} & B\\ \end{array} \right)$ be APT, then for every unitarily invariant norm $|| \cdot ||$ and some unitary matrix $U\in \mathbb{M}_n,$

Squaring the inequalities in Corollary 2.6, we get a quick consequence.

Corollary 2.7. If $M = \left(\begin{array}{cc} A & X \\ Y^{*} & B\\ \end{array} \right)$ is APT, then

Proof: Compute

It is known that for any $X, Y\in \mathbb{M}_n$ and any indices $i, j$ such that $i+j\leq n+1$, we have $s_{i+j-1}(XY)\leq s_i(X)s_j(Y)$ (see [2, Page 75]). By utilizing this fact and Theorem 2.4, we can obtain the following result.

Corollary 2.8. Let $M = \left(\begin{array}{cc} A & X \\ Y^{*} & B\\ \end{array} \right)$ be APT, then for any $t\in [0, 1]$, we have

Consequently,

Proof: By Lemma 2.1 and Theorem 2.4, observe that

Finally, we study the relationship between the diagonal blocks and the real part of the off-diagonal blocks of the APT matrix $M$.

Theorem 2.9. Let $M = \left(\begin{array}{cc} A & X \\ Y^{*} & B\\ \end{array} \right)$ be APT, then for all $t\in [0, 1]$,

and

Proof: Since $M$ is APT, we have that

is PPT.

Therefore,

So, by Lemma 2.1, we have

This implies the first inequality.

Since ${{{\rm{Re\, }}}} M$ is PPT, we have

Thus,

is PPT.

By Lemma 2.3,

is also PPT.

So,

which means that

By Lemma 2.1, we have

This completes the proof.

Corollary 2.10. Let $\left(\begin{array}{cc} {{{\rm{Re\, }}}} A & \frac{X+Y}{2} \\ \frac{X+Y}{2} & {{{\rm{Re\, }}}} B\\ \end{array} \right)\geq0.$ If $\frac{X+Y}{2}$ is Hermitian and $t\in[0, 1]$, then,

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The work is supported by National Natural Science Foundation (grant No. 12261030), Hainan Provincial Natural Science Foundation for High-level Talents (grant No. 123RC474), Hainan Provincial Natural Science Foundation of China (grant No. 124RC503), the Hainan Provincial Graduate Innovation Research Program (grant No. Qhys2023-383 and Qhys2023-385), and the Key Laboratory of Computational Science and Application of Hainan Province.

Conflict of interest

The authors declare that they have no conflict of interest.