zbMATH — the first resource for mathematics

Symmetric matrices whose entries are linear functions. (English. Russian original) Zbl 07264244
Comput. Math. Math. Phys. 60, No. 1, 102-108 (2020); translation from Zh. Vychisl. Mat. Mat. Fiz. 60, No. 1, 109-115 (2020).
The author considers matrices \(A\) whose entries are linear functions in several real variables. In particular, he studies the problem of understanding when such matrices are positive (or negative) definite at some point. The author’s motivation comes mainly form semidefinite programming problems, where the search for a point at which a matrix is definite is important.
The author first defines the notion of a property that holds for almost every matrix and stresses that such a notion plays an important role in the development of heuristic algorithms. Given a set of matrices with entries depending on parameters \(\xi_{1},\xi_{2},\ldots ,\xi_{m}\), some property \(\Phi (\xi_{1},\xi_{2},\ldots ,\xi_{m})\) holds for almost every matrix of this set if there exists a polynomial \(p(\xi_{1},\xi_{2},\ldots ,\xi_{m})\), not identical to zero, such that for each set of values \(\xi_{1},\xi_{2},\ldots ,\xi_{m}\) if the property \(\Phi (\xi_{1},\xi_{2},\ldots ,\xi_{m})\) does not hold, then the polynomial vanishes: \[ p(\xi_{1},\xi_{2},\ldots ,\xi_{m})=0. \]
In the paper the following results are proved:
1) For almost every \(n\times n\) matrix \(A\) whose entries are linear functions in \(n\) variables, there exists a point at which the determinant of \(A\) is positive and there exists another point at which the determinant of \(A\) is negative. The same is true for almost every symmetric \(n\times n\) matrix of the considered form.
2) For almost all sets of linear functions \(\ell_{0},\ell_{1},\ldots ,\ell_{n}\) in \(n\) variables \(x_{1},x_{2}, \ldots ,x_{n}\) and for any \(n\times n\) matrix \(M\), the matrix \[ \ell_{0}M+\operatorname{diag}\left( \ell_{1},\ell_{2},\ldots ,\ell_{n}\right) \] is definite at some point (here \(\operatorname{diag}\left( \ell_{1},\ell_{2},\ldots ,\ell_{n}\right) \) denotes the diagonal matrix with entries \(\ell_{1}, \ell_{2},\ldots ,\ell_{n}\) on the main diagonal). In particular, almost every symmetric \(2\times 2\) matrix whose entries are linear functions in two variables is definite at some point.
3) For almost all sets of linear functions \(\ell_{1}, \ell_{2},\ldots ,\ell_{n}\) in \(n\) variables \(x_{1},x_{2}, \ldots ,x_{n}\) and for any numerical \(n\times n\) matrix \(M\), the matrix \(M+\operatorname{diag}\left( \ell_{1},\ell_{2},\ldots ,\ell_{n}\right) \) is positive definite at some point and negative definite at another point.
4) For all triplets of linear functions \(\ell_{0},\ell_{1},\ell_{2}\) in two variables \(x_{1}\) and \(x_{2}\), if \(\ell_{0}(0,0)\neq 0\), then the symmetric \(3\times 3\) matrix \[ \begin{bmatrix} x_{1} & \ell_{0} & \ell_{1} \\ \ell_{0} & x_{2} & \ell_{2} \\ \ell_{1} & \ell_{2} & x_{3} \end{bmatrix} \] is definite at some point. The author also presents an example which shows that the condition \(\ell_{0}(0,0)\neq 0\) is essential.
At the end of the paper, the above results are illustrated by using Hessian matrices of third-degree polynomials.
15B57 Hermitian, skew-Hermitian, and related matrices
15A54 Matrices over function rings in one or more variables
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
90C22 Semidefinite programming
Full Text: DOI
[1] Zabotin, V. I.; Chernyaev, Yu. A., Newton’s method for minimizing a convex twice differentiable function on a preconvex set, Comput. Math. Math. Phys., 58, 322-327 (2018) · Zbl 1397.90397
[2] Vorob’ev, N. N.; Grigor’ev, D. Yu., Finding connected components of a semialgebraic set in subexponential time, J. Math. Sci., 70, 1847-1872 (1994) · Zbl 0835.68061
[3] Evtushenko, Yu. G.; Posypkin, M. A.; Rybak, L. A.; Turkin, A. V., Finding sets of solutions to systems of nonlinear inequalities, Comput. Math. Math. Phys., 57, 1241-1247 (2017) · Zbl 1381.65044
[4] Safey El Din, M.; Schost, E., A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets, J. ACM, 63, 48 (2017) · Zbl 1426.68311
[5] Hillar, C. J.; Lim, L.-H., Most tensor problems are NP-hard, J. ACM, 60, 45 (2013) · Zbl 1281.68126
[6] Sal’kov, N. A., General principles for formation of ruled surfaces. Part 1, Geom. Grafika, 6, 20-31 (2018)
[7] Zhadan, V. G., Primal Newton method for the linear cone programming problem, Comput. Math. Math. Phys., 58, 207-214 (2018) · Zbl 1397.90269
[8] Renegar, J., Accelerated first-order methods for hyperbolic programming, Math. Program. Ser. A, 173, 1-35 (2019) · Zbl 1410.90159
[9] Lourenco, B. F.; Kitahara, T.; Muramatsu, M.; Tsuchiya, T., An extension of Chubanov’s algorithm to symmetric cones, Math. Program. Ser. A, 173, 117-149 (2019) · Zbl 1410.90158
[10] Aravkin, A. Y.; Burke, J. V.; Drusvyatskiy, D.; Friedlander, M. P.; Roy, S., Level-set methods for convex optimization, Math. Program. Ser. B, 174, 359-390 (2019) · Zbl 1421.90111
[11] Laurent, M.; Varvitsiotis, A., Positive semidefinite matrix completion, universal rigidity, and the strong Arnold property, Linear Algebra Appl., 452, 292-317 (2014) · Zbl 1291.90165
[12] A. Kurpisz, S. Leppanen, and M. Mastrolilli, “Sum-of-squares hierarchy lower bounds for symmetric formulations,” Math. Program. Ser. A (2019). 10.1007/s10107-019-01398-9. · Zbl 1419.90070
[13] Braun, G.; Pokutta, S.; Zink, D., Affine reductions for LPs and SDPs, Math. Program. Ser. A, 173, 281-312 (2019) · Zbl 1410.90147
[14] Huang, Z.; Zhan, X., Nonsymmetric normal entry patterns with the maximum number of distinct indeterminates, Linear Algebra Appl., 485, 359-371 (2015) · Zbl 1322.05031
[15] Van, H. H.; Quinlan, R., On the maximum rank of completions of entry pattern matrices, Linear Algebra Appl., 525, 1-19 (2017) · Zbl 1365.15004
[16] Van, H. H.; Quinlan, R., Almost-nonsingular entry pattern matrices, Linear Algebra Appl., 578, 334-355 (2019) · Zbl 1418.15026
[17] Brualdi, R. A.; Huang, Z.; Zhan, X., Singular, nonsingular, and bounded rank completions of ACI-matrices, Linear Algebra Appl., 433, 1452-1462 (2010) · Zbl 1205.15042
[18] McTigue, J.; Quinlan, R., Partial matrices of constant rank, Linear Algebra Appl., 446, 177-191 (2014) · Zbl 1286.15032
[19] Borobia, A.; Canogar, R., ACI-matrices of constant rank over arbitrary fields, Linear Algebra Appl., 527, 232-259 (2017) · Zbl 1365.15036
[20] A. Yu. Nikitin and A. N. Rybalov, “On complexity of the satisfiability problem of systems over finite posets,” Prikl. Diskret. Mat., No. 39, 94-98 (2018). 10.17223/20710410/39/8
[21] Rybalov, A. N., Generic amplification of recursively enumerable sets, Algebra Logic, 57, 289-294 (2018) · Zbl 1439.03078
[22] A. N. Rybalov, “On generic complexity of decidability problem for Diophantine systems in the Skolem’s form,” Prikl. Diskret. Mat., No. 37, 100-106 (2017). 10.17223/20710410/37/8
[23] Malashonok, G. I., MathPartner computer algebra, Program. Comput. Software, 43, 112-118 (2017)
[24] Smirnov, A. V., The bilinear complexity and practical algorithms for matrix multiplication, Comput. Math. Math. Phys., 53, 1781-1795 (2013) · Zbl 1313.65094
[25] Smirnov, A. V., A bilinear algorithm of length 22 for approximate multiplication of 2 × 7 and 7 × 2 matrices, Comput. Math. Math. Phys., 55, 541-545 (2015) · Zbl 1331.68296
[26] Pan, V. Ya., Fast matrix multiplication and its algebraic neighborhood, Sb. Math., 208, 1661-1704 (2017) · Zbl 06856672
[27] Cenk, M.; Hasan, M. A., On the arithmetic complexity of Strassen-like matrix multiplications, J. Symbolic Comput., 80, 484-501 (2017) · Zbl 1353.68309
[28] Dolgov, D. A., Polynomial greatest common divisor as a solution of system of linear equations, Lobachevskii J. Math., 39, 985-991 (2018) · Zbl 1444.11006
[29] Bernardi, A.; Blekherman, G.; Ottaviani, G., On real typical ranks, Boll. Unione Mat. Ital., 11, 293-307 (2018) · Zbl 1403.15018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.