On unique solvability
of the piecewise linear equation system

Shubham Kumar$^\ast $ Deepmala$^{\ast \ast }$

August 23, 2022; accepted: November 9, 2022; published online: December 31, 2022.

In this article, we take the piecewise linear equation system $x-W|x|=b$, which is also known as the absolute value equation, where W $\in $ ${\mathbb R}^{n\times n}$, b $\in $ ${\mathbb R}^{n}$ are given and to determine the value of $x$ $\in $ ${\mathbb R}^{n}$. The absolute value equation (AVE) has many applications in various fields of mathematics like bi-matrix games, linear interval systems, linear complementarity problems (LCP) etc. By the equivalence relation of AVE with LCP, some necessary and sufficient conditions proved the existence and unique solvability of the AVE. Some examples are also provided to highlight the current singular value conditions for a unique solution that may revise in the future.

MSC. 90C05, 90C30, 15A18.

Keywords. Unique solvability, Absolute value equation, Linear complementarity problem.

$^\ast $This research work of the first author is supported by the Ministry of Education (Government of India) through GATE fellowship registration No. MA19S43033021.

$^\ast $Mathematics Discipline, PDPM-Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, M.P., India, e-mail: shub.srma@gmail.com

$^{\ast \ast }$Mathematics Discipline, PDPM-Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, M.P., India, e-mail: dmrai23@gmail.com

1 Introduction

Here we study the AVE (absolute value equation) of the type

\begin{equation} \label{Equ1} x-W|x| = b, \end{equation}

where $W \in {\mathbb R}^{n \times n}$, $b\in {\mathbb R}^{n}$ are known, and $x \in {\mathbb R}^{n}$ is unknown; $|\cdot |$ denotes the absolute value operator. For a matrix $W\in {\mathbb R}^{n \times n}$ and a vector $x \in {\mathbb R}^{n}$, $\vert W \vert $ and $\vert x \vert $ denote the component-wise absolute value of the matrix and the vector, respectively.

The generalized absolute value equation (GAVE) is the standard form of (1) defined as

\begin{equation} \label{Equ3i} Vx-W|x| = b, \end{equation}

where $V, W\in {\mathbb R}^{n \times n}$, $b\in {\mathbb R}^{n}$ are given while $x\in {\mathbb R}^{n}$ is to be determined.

In the literature, many authors discussed its unique solvability (see [ 1 , 16 , 18 , 22 , 23 ] and the references therein) and its particular case, when $W=I$, i.e.,

\begin{equation} \label{Equ2} Vx-|x| = b, \end{equation}

is discussed in ( [ 7 , 8 , 12 , 20 , 21 ] and the references therein).

To the best of our knowledge, another particular case of Eq.(2) as $V=I$ have not been discussed for the sufficient condition of unique solvability aspects in the literature in a strong way to date. In 2014, Jiri Rohn [ 19 ] took the particular case of (1) as $W$ $\ge $ 0 and discussed the unique solution condition with restrictions on $W$ and $b$. In [ 6 ] , authors provided some conditions for the bounding solution of AVE (1). The study of the AVE (1) is challenging and interesting, as it contains non-linear and non-differential terms $W|x|$. Currently, many methods to solve AVE available in the literature, like the linear programming method [ 11 ] , globally and quadratically convergent method [ 3 ] , matrix multi-splitting Picard-iterative method [ 5 ] , generalized Newton method [ 10 ] , iterative method [ 18 ] and for more, one may refer to [ 2 , 13 , 17 ] . In recent years, some authors investigated the existence and uniqueness of different types of AVE (see [ 8 , 9 , 15 , 16 , 20 , 26 ] and references therein).

Throughout the paper, we will denote $ \hat{D}= \operatorname {diag}(\hat{d_i})$ with $\hat{d_i} \in [{0,1}]$ is a diagonal matrix. For a matrix $A$, $\sigma _{1}(A)$ or $\sigma _{\max }(A)$ and $\sigma _{n}(A)$ or $\sigma _{\min }(A)$ will denote the maximum singular value and the minimum singular value of A, respectively.

The structure of the paper is the following: in section 2 we recall some necessary definitions and results that will be used throughout the paper. In section 3, with the help of LCP, some unique solution results are established for 1. Finally, the conclusions are discussed in section 4.

2 Preliminaries

Here, we recall some definitions and lemmas for additional results.

Definition 1

The LCP(q,M) is defined as [ 4 ] :

\begin{align} \label{Equ4} 0 \leq z \perp Mz + q \geq 0 \end{align}

where $q, z \in {\mathbb R}^n $, $M \in {\mathbb R}^{n \times n}$.

Definition 2 [ 14 ]

A square matrix is called a P-matrix if all its principal minors are positive. Furthermore, every positive definite matrix is a P-matrix.

Lemma 3 [ 4 ]

A matrix M is a P-matrix if and only if the LCP(q,M) has a unique solution for any q.

Lemma 4 [ 24 ]

Let A $\in C^{m \times m}$ satisfy the condition $\| A\| _2 {\lt} 1$. Then A$\pm $I is non-singular.

Lemma 5 [ 3 ]

Let $\| A^{-1}\| _2 {\lt} 1$. Then $A+\bar{D}$ is non-singular for any diagonal matrix $\bar{D} = \operatorname {diag}(\bar{d}_i)$ with $-1 \leq \bar{d}_i \leq 1$.

Lemma 6 [ 22 ]

If the maximum singular value of the matrix W is strictly less than $1$, then AVE 1 has a unique solution.

Lemma 7 [ 4 ]

A matrix M is called a Q-matrix if, for any $q\in $ ${\mathbb R}^{n}$, LCP(q,M) has a solution.

Lemma 8 [ 23 ]

The AVE 2 has a unique solution if and only if matrix $V+W-2W\hat{D}$ or $V-W+2W\hat{D}$ is non-singular for any diagonal matrix $\hat{D}$.

Lemma 8 is equivalent to the following lemma when W is a non-singular matrix.

Lemma 9

The AVE 2 has a unique solution if and only if matrix

\[ W(W^{-1}V + I-2\hat{D}) \]

\[ W(W^{-1}V-I+2\hat{D}) \]

is non-singular for any diagonal matrix $\hat{D}$.

Lemma 10 [ 25 ]

For square matrices $A$ and $B$, singular value inequality $\sigma _{i}(A+B)$ $\ge $ $\sigma _{i}(A) $ $-$ $\sigma _{1}(B)$, $i=1,2,\ldots ,n$ holds.

3 Main Results

In this section, we introduce significant results for the unique solution of AVE 1 and GAVE 2 and establish an equivalence relation between AVE and LCP. With the help of this relation, we get some results for the AVE 1.

Theorem 11

If matrix $(I-W)$ is non-singular, then the following results are equivalent:
1. for any b, the AVE 1 has a unique solution;
2. matrix $(I-W)^{-1}(I+W)$ is a P-matrix;
3. matrix $(I-W)^{-1}(I+W)$ is a positive definite matrix;
4. all the principal minors of the matrix $(I-W)^{-1}(I+W)$ are positive.

Proof â–¼

Let $x_i^{+} = \max _i(0,x_i)$ and $x_i^{-} = \max _i(0,-x_i) $. So

\begin{equation} \label{Equ5} x =x^{+}- x^{-} \quad \textrm{and} ~ ~ |x| =x^{+}+ x^{-} \end{equation}

Now by 5, AVE 1 is rewritten as

\begin{equation} \label{Equ6} x^{+}= (I-W)^{-1}(I+W)x^{-} + (I-W)^{-1}b. \end{equation}

6 is a LCP form, where M= $(I-W)^{-1}(I+W)$.

Then, by lemma 3 and definition 2, our results hold.

Proof â–¼

Based on lemma 7, we get the existence result for 1 in theorem 12.

Theorem 12

If $(I-W)$ is non-singular matrix then for any $b$, AVE 1 has a solution, if $(I-W)^{-1}(I+W)$ is a $Q$-matrix.

Proof â–¼

If matrix $(I-W)$ is non-singular, then 1 can be written as the given below form:

\begin{equation*} \label{Equ6i} x^{+}= (I-W)^{-1}(I+W)x^{-} + (I-W)^{-1}b, \end{equation*}

where $x^{+}$ and $x^{-}$ are defined in 5. Which is a linear complementarity problem form. Then, with the help of lemma 7, we get our result.

Proof â–¼

Now, by substituting $V=I$ in lemma 8, we will get the necessary and sufficient conditions for AVE 1 see theorem 13 and theorem 14.

Theorem 13

For any diagonal matrix $\hat{D}$, the matrix

\[ (I-W+2W\hat{D}) \]

is non-singular if and only if for any $b$, AVE 1 has a unique solution.

Theorem 14

For any diagonal matrix $\hat{D}$, the matrix $(I+W-2W\hat{D})$ is non-singular if and only if there exists a unique solution of AVE 1 for any $b$.

Based on the simple result “if the smallest singular value of a matrix is greater than $0$, then the given matrix is non-singular", we get the following two results, see theorem 15 and theorem 16.

Theorem 15

If $\sigma _{\min }(I+W){\gt}$ $2\sigma _{\max }(W\hat{D})$ or $\sigma _{\min }(I-W){\gt}$ $2\sigma _{\max }(W\hat{D})$ for any diagonal matrix $\hat{D}$, then there exists a unique solution of AVE 1 for any $b$.

Proof â–¼

By lemma 10, we have $\sigma _{\min }(I+W-2W\hat{D}) \ge $ $\sigma _{\min }(I+W)-$ $2\sigma _{\max }(W\hat{D}).$

If $\sigma _{\min }(I+W)$ ${\gt}$ $2\sigma _{\max }(W\hat{D})$, then matrix $I+W-2W\hat{D}$ is nonsingular for any diagonal matrix $\hat{D}$. So by the previous result of the theorem 14, AVE 1 has a unique solution. By Similar way with the help of theorem 13 we can prove that if $\sigma _{\min }(I-W)$ ${\gt}$ $2\sigma _{\max }(W\hat{D})$ then AVE 1 has a unique solution.

Proof â–¼

Moreover, the result of the theorem 15 can be extended for the GAVE 2.

Theorem 16

If $\sigma _{\min }(W(2\hat{D}-I)){\gt}1$ for any diagonal matrix $\hat{D}$, then AVE 1 has a unique solution for any $b$.

Proof â–¼

Based on lemma 10, we have

\[ \sigma _{\min }(I-W+2W\hat{D})\ge \sigma _{\min }(2W\hat{D}-W)-\sigma _{\max }(I). \]

Since $\sigma _{\max }(I)=1$, so if $\sigma _{\min }(2W\hat{D}-W){\gt}1$ then matrix $I+W-2W\hat{D}$ is nonsingular for any diagonal matrix $\hat{D}$, so the AVE 1 has a unique solution for any $b$.

Proof â–¼

Based on lemma 4, we get the following result for GAVE 2.

Theorem 17

For any diagonal matrix $\hat{D}$, if $\Vert W^{-1}V-2\hat{D}\Vert _2 {\lt} 1$ or $\Vert W^{-1}V+2\hat{D}\Vert _2 {\lt} 1$ then for any b, the AVE 2 has a unique solution, where $W$ is a non-singular matrix.

Proof â–¼

By the help of lemma 4, if $\Vert W^{-1}V-2\hat{D}\Vert _2 {\lt} 1$, then $W^{-1}V-2\hat{D}+I$ is non-singular, since W is non-singular, so $W[W^{-1}V-2\hat{D}+I]$ is also non-singular, then by lemma 9, AVE 2 has a unique solution for any $b$.

Or, when $\Vert W^{-1}V+2\hat{D}\Vert _2 {\lt} 1$, then matrix $W^{-1}V+2\hat{D}-I$ is non-singular, so $W[W^{-1}V+2\hat{D}-I]$ is also non-singular, then by lemma 9, AVE 2 has a unique solution for any $b$.

Proof â–¼

Corollary 18

There exists a unique solution of AVE 3 if $\Vert (V+2\hat{D})\Vert _2 {\lt} 1$ or $\Vert (V-2\hat{D})\Vert _2 {\lt} 1$ for any diagonal matrix $\hat{D}$.

By substituting $W=I$ in theorem 17, then corollary 18 will become the main result of the [ 21 , Th. 3.4 ] ).

Based on theorem 13, theorem 14 and lemma 4, we get the following result.

Theorem 19

For any diagonal matrix $\hat{D}$, matrix W satisfies $\Vert W-2W\hat{D}\Vert _2 {\lt} 1$ or $\Vert -W+2W\hat{D}\Vert _2 {\lt} 1$ then for any b, AVE 1 has a unique solution.

Proof â–¼

With the aid of lemma 4, if $\Vert W-2W\hat{D}\Vert _2 {\lt} 1$, then $W-2W\hat{D}+I$ is non-singular, then by theorem 14, AVE 1 has unique solution.

Or, when $\Vert -W+2W\hat{D}\Vert _2 {\lt} 1$, then matrix $-W+2W\hat{D}+I$ is non-singular, then by theorem 13, AVE 1 has unique solution.

Proof â–¼

Based on lemma 5 and lemma 8, we get the following result.

Theorem 20

If matrix V and non-singular matrix W will satisfy the conditions $\Vert (W^{-1}V-I)^{-1}\Vert _2 {\lt} 2$ or $\Vert (W^{-1}V+I)^{-1}\Vert _2 {\lt} 2$ then for any b, AVE 2 has a unique solution.

Proof â–¼

Let

\begin{equation} \begin{split} \label{Equ19 i} (i) ~ (V-W+2W\hat{D}) = 2W\left[\tfrac {1}{2}{W^{-1}{(V-W)}}+\hat{D}\right] \\ (ii)~ (V+W-2W\hat{D}) = 2W\left[\tfrac {1}{2}{W^{-1}{(V+W)}}-\hat{D}\right]. \end{split}\end{equation}

With the aid of lemma 5, when $\Vert \frac{1}{2}(W^{-1}V-I)^{-1}\Vert _2 {\lt} 1$, then $\frac{1}{2}(W^{-1}V-I)+\hat{D} $ is non-singular. By 8 and lemma 8 our proof is complete.

Or, when $\Vert \frac{1}{2}(W^{-1}V+I)^{-1}\Vert _2 {\lt} 1$, then matrix $\frac{1}{2}(W^{-1}V+I)-\hat{D} $ is non-singular. Then, by 8 and lemma 8 our proof is completed.

Proof â–¼

Corollary 21

There exists a unique solution of AVE 3 if $\Vert (V-I)^{-1}\Vert _2 {\lt} 2$ or $\Vert (V+I)^{-1}\Vert _2 {\lt} 2$.

By substituting $W=I$ in theorem 20, then corollary 21 will become Theorem 3.5 as a main result in [ 21 ] .

Corollary 22

If $\Vert (W^{-1}-I)^{-1}\Vert _2 {\lt} 2$ or $\Vert (W^{-1}+I)^{-1}\Vert _2 {\lt} 2$, then there exists a unique solution of AVE 1.

We get our result by substituting $V=I$ in theorem 20.

Remark 23

Sometime the condition $\Vert (V-I)^{-1}\Vert _2 {\lt} 2$ given in corollary 21 is not satisfying even AVE $Vx-|x|=b$ has a unique solution. â–¡

Let us consider the following example.

Example 24

The AVE $Vx-|x|=(2,-2)^T$ ($T$ denotes the transpose of the vector $(2,-2)$) has a unique solution $x=(20,-0.909091)^T$, for

\begin{equation*} V= \begin{bmatrix} 1.1 & 0.0 \\ 0.0 & 1.2 \end{bmatrix} . \end{equation*}

Clearly, $\Vert (V-I)^{-1}\Vert _2 = 10 \nless 2.$

Remark 25

By the result $\sigma _{\max }(W)$$\sigma _{\min }(W^{-1}) =1 $, the condition $\sigma _{\max }(W) {\lt} 1$ of lemma 6 is equivalent to the condition $\sigma _{\min }(W^{-1}) {\gt} 1.$ Sometimes, matrix $W$ does not satisfy the conditions $\sigma _{\max }(W) {\lt} 1$ or $\sigma _{\min }(W^{-1}) {\gt} 1$ but AVE 1 has a unique solution for some $b.$ â–¡

Let us consider the following example.

Example 26

Consider the matrix

\begin{equation*} W= \begin{bmatrix} -0.9 & 0.2 \\ -0.4 & -0.8 \end{bmatrix}. \end{equation*}

Here $\sigma _{\min }(W^{-1}) = 0.9870 \ngtr 1 $ and $\sigma _{\max }(W) = 1.0132 \nless 1$, even AVE $x-W|x|=b$ has a unique solution $x=(2.66667,-15.33334)^{T}$ for some $b=(2,-2)^T$ ($T$ denotes the transpose).

Furthermore, the conditions $\sigma _{\min }(W) {\lt} 1$ and $\sigma _{\max }(W^{-1}) {\gt} 1$ maybe replace the existing conditions $\sigma _{\max }(W) {\lt} 1$ and $\sigma _{\min }(W^{-1}) {\gt} 1$ respectively, because of we have inequalities $\sigma _{\min }(W) \le \sigma _{\max }(W) {\lt} 1$ and $\sigma _{\max }(W^{-1}) \ge \sigma _{\min }(W^{-1}) {\gt} 1$. Also for example 26 we have $\sigma _{\max }(W^{-1}) = 1.2665{\gt}1$ and $\sigma _{\min }(W) =0.7896{\lt}1$. So existing singular value conditions may be revised in future. This needs further investigation. These conditions may be or may not be superior then the current singular value conditions.

4 Conclusion

This article discusses the existence of solution possibilities in the uniqueness of the GAVE $Vx -W|x|=b$ and its particular cases. The conditions of lemma 6, corollary 21 and corollary 22 may be revised in the future. With the help of the equivalence relation of LCP and AVE, we established some more conditions for the unique solvability of 1. The numerical results for the absolute value equations are also an interesting topic in the future.

Acknowledgements

The authors are thankful to the anonymous referees for their insightful comments, which significantly improved the manuscript.

Bibliography

1: M. Achache, On the unique solvability and numerical study of absolute value equations, J. Numer. Anal. Approx. Theory, 48 (2019) no. 2, pp. 112–121. https://doi.org/10.33993/jnaat482-1182 $\includegraphics[scale=0.1]{ext-link.png}$
2: N. Anane, M. Achache, Preconditioned conjugate gradient methods for absolute value equations, J. Numer. Anal. Approx. Theory, 49 (2020) no. 1, pp. 3–14. https://doi.org/10.33993/jnaat491-1197 $\includegraphics[scale=0.1]{ext-link.png}$
3: L. Caccetta, B. Qu, G.L. Zhou, A globally and quadratically convergent method for absolute value equation, Comput. Optim. Appl., 48 (2011), pp. 45–58. https://doi.org/10.1007/s10589-009-9242-9 $\includegraphics[scale=0.1]{ext-link.png}$
4: R.W. Cottle, J.S. Pang, R.E. Stone, The Linear Complementarity Problem, Acad. Press, New York, 1992.
5: M. Dehghan, A. Shirilord, Matrix multisplitting Picard-iterative method for solving generalized absolute value matrix equation, Appl. Numer. Math., 158 (2020), pp. 425–438. https://doi.org/10.1016/j.apnum.2020.08.001 $\includegraphics[scale=0.1]{ext-link.png}$
6: M. Hladik, Bounds for the solutions of absolute value equations, Comput. Optim. Appl., 69 (2018), pp. 243-–266. https://doi.org/10.1007/s10589-017-9939-0 $\includegraphics[scale=0.1]{ext-link.png}$
7: S.L. Hu, Z.H. Huang, A note on absolute value equations, Optim. Lett., 4 (2010), pp. 417–424. https://doi.org/10.1007/s11590-009-0169-y $\includegraphics[scale=0.1]{ext-link.png}$
8: O.L. Mangasarian, R.R. Meyer, Absolute value equations, Linear Algebra Appl., 419 (2006), pp. 359–367. https://doi.org/10.1016/j.laa.2006.05.004 $\includegraphics[scale=0.1]{ext-link.png}$
9: O.L. Mangasarian, Absolute value programming, Comput. Optim. Appl., 36 (2007) no. 1, pp. 43–53. https://doi.org/10.1007/s10589-006-0395-5 $\includegraphics[scale=0.1]{ext-link.png}$
10: O.L. Mangasarian, A generalized Newton method for absolute value equations, Optim. Lett., 3 (2009), pp. 101–108. https://doi.org/10.1007/s11590-008-0094-5 $\includegraphics[scale=0.1]{ext-link.png}$
11: O.L. Mangasarian, Absolute Value equation solution via linear programming, J. Optim. Theory Appl., 161 (2014), pp. 870–876. https://doi.org/10.1007/s10957-013-0461-y $\includegraphics[scale=0.1]{ext-link.png}$
12: O.L. Mangasarian, Sufficient conditions for the unsolvability and solvability of the absolute value equation. Optim. Lett., 11 (2017), pp. 1469–1475. https://doi.org/10.1007/s11590-017-1115-z $\includegraphics[scale=0.1]{ext-link.png}$
13: L. Abdallah, M. Haddou, T. Migot, Solving absolute value equation using complementarity and smoothing functions, J. Comp. Appl. Math., 327 (2018), pp. 196–207. https://doi.org/10.1016/j.cam.2017.06.019 $\includegraphics[scale=0.1]{ext-link.png}$
14: K.G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Internet edition, 1997.
15: J. Rohn, A theorem of the alternatives for the equation $Ax + B|x| = b,$ Linear Multilinear Algebra, 52 (2004) no. 6, pp. 421–426. https://doi.org/10.1080/0308108042000220686 $\includegraphics[scale=0.1]{ext-link.png}$
16: J. Rohn, On unique solvability of the absolute value equation, Optim. Lett., 3 (2009), pp. 603–606. https://doi.org/10.1007/s11590-009-0129-6 $\includegraphics[scale=0.1]{ext-link.png}$
17: J. Rohn, An algorithm for solving the absolute value equations, Electron. J. Linear Algebra, 18 (2009), pp. 589–599. https://doi.org/10.13001/1081-3810.1332 $\includegraphics[scale=0.1]{ext-link.png}$
18: J. Rohn, V. Hooshyarbakhsh, R. Farhadsefat, An iterative method for solving absolute value equations and sufficient conditions for unique solvability, Optim. Lett., 8 (2014), pp. 35–44. https://doi.org/10.1007/s11590-012-0560-y $\includegraphics[scale=0.1]{ext-link.png}$
19: J. Rohn, A class of explicitly solvable absolute value equations, Technical report V-1202, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague (2014).
20: S.L. Wu, P. Guo, On the unique solvability of the absolute value equation, J. Optim. Theory Appl., 169 (2016), pp. 705–712. https://doi.org/10.1007/s10957-015-0845-2 $\includegraphics[scale=0.1]{ext-link.png}$
21: S.L. Wu, C.X. Li, The unique solution of the absolute value equations, Appl. Math. Lett., 76 (2018), pp. 195–200. https://doi.org/10.1016/j.aml.2017.08.012 $\includegraphics[scale=0.1]{ext-link.png}$
22: S.L. Wu, C.X. Li, A note on unique solvability of the absolute value equation, Optim. Lett., 14 (2019), pp. 1957–1960.
23: S.L. Wu, S. Shen, On the unique solution of the generalized absolute value equation, Optim. Lett., 15 (2021), pp. 2017–2024. https://doi.org/10.1007/s11590-020-01672-2 $\includegraphics[scale=0.1]{ext-link.png}$
24: W.S. Zhang, Finite Difference Methods for Partial Differential Equations in Science Computation, Higher Education Press, 2006.
25: F. Zhang, Matrix Theory: Basic results and techniques, 2nd ed., Springer, New York, 2011.
26: H. Zhou, S. Wu, On the unique solution of a class of absolute value equations $Ax-B|Cx|=d$, AIMS Math., 6 (2021) no. 8, pp. 8912–8919. https://doi.org/10.3934/math.2021517 $\includegraphics[scale=0.1]{ext-link.png}$

On unique solvability of the piecewise linear equation system

1 Introduction

2 Preliminaries

3 Main Results

4 Conclusion

Bibliography

On unique solvability
of the piecewise linear equation system