Search

Let $P(\lambda) = A_0 + \lambda A_1$ be a singular $m\times n$ matrix pencil without full rank whose Kronecker canonical form (KCF) is given. Let r be a positive integer such that $\rho \leq \min\{m,n\}- {\rm rank} (P)$ and $\rho \leq {\rm rank}(P)$. We study the change of the KCF of $P(\lambda)$ due to perturbation pencils $Q(\lambda)$ with ${\rm rank} (Q) = \rho$. We focus on the generic behavior of the KCF of $(P+Q)(\lambda)$, i.e., the behavior appearing for perturbations $Q(\lambda)$ in a dense open subset of the pencils with rank r. The most remarkable generic properties of the KCF of the perturbed pencil $(P+Q) (\lambda)$ are (i) if $\lambda_0$ is an eigenvalue of $P(\lambda)$, finite or infinite, then $\lambda_0$ is an eigenvalue of $(P+Q)(\lambda)$; (ii) if $\lambda_0$ is an eigenvalue of $P(\lambda)$, then the number of Jordan blocks associated with $\lambda_0$ in the KCF of $(P+Q) (\lambda)$ is equal to or greater than the number of Jordan blocks associated with $\lambda_0$ in the KCF of $P(\lambda)$; (iii) if $\lambda_0$ is an eigenvalue of $P(\lambda)$, then the dimensions of the Jordan blocks associated with $\lambda_0$ in $(P+Q) (\lambda)$ are equal to or greater than the dimensions of the Jordan blocks associated with $\lambda_0$ in $P (\lambda)$; (iv) the row (column) minimal indices of $(P+Q) (\lambda)$ are equal to or greater than the largest row (column) minimal indices of $P(\lambda)$. Moreover, if the sum of the row (column) minimal indices of the perturbations $Q(\lambda)$ is known, apart from their rank, then the whole set of the row (column) minimal indices of $(P+Q) (\lambda)$ is generically obtained, and in the case $\rho < \min\{m,n\}- {\rm rank} (P)$ the whole KCF of $(P+Q) (\lambda)$ is generically determined.

The development of fast algorithms for performing computations with n x n low-rank structured matrices has been a very active area of research during the last two decades, as a consequence of the numerous applications where these matrices arise. The key ideas behind these fast algorithms are that low-rank structured matrices can be described in terms of O(n) parameters and that these algorithms operate on the parameters instead on the matrix entries. Therefore, the sensitivity of any computed quantity should be measured with respect to the possible variations that the parameters de ning these matrices may su er, since this determines the maximum accuracy of a given fast computation. In other words, it is necessary to develop condition numbers with respect to parameters for di erent magnitudes and classes of low-rank structured matrices, but, as far as we know, this has not yet been accomplished in any case. In this paper, we derive structured relative eigenvalue condition numbers for the important class of low-rank structured matrices known as {1;1}-quasiseparable matrices with respect to relative perturbations of the parameters in the quasiseparable and in the Givens-vector representations of these matrices, and we provide fast algorithms for computing them. Comparisons among the new structured condition numbers and the unstructured one are also presented, as well as numerical experiments showing that the structured condition numbers can be small in situations where the unstructured one is huge. In addition, the approach presented in this paper is general and may be extended to other problems and classes of low-rank structured matrices. This research was partially supported by Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542. Publicado

The matrix Sylvester equation for congruence, or T-Sylvester equation, has recently attracted considerable attention as a consequence of its close relation to palindromic eigenvalue problems. The theory concerning T-Sylvester equations is rather well understood and there are stable and e cient numerical algorithms which solve these equations for small- to medium-sized matrices. However, developing numerical algorithms for solving large-scale T-Sylvester equations still remains an open problem. In this paper, we present several projection algorithms based on di erent Krylov spaces for solving this problem when the right-hand side of the T-Sylvester equation is a low-rank matrix. The new algorithms have been extensively tested, and the reported numerical results show that they work very well in practice, o ering a clear guidance on which algorithm is the most convenient in each situation. This work has been supported by Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542. Publicado

The proceeding at: Joint ALAMA-GAMM/ANLA 2014 Meeting, took place 2014, July 14-16, in Barcelona (Spain). We present necessary and su cient conditions for the existence of a matrix polynomial when its degree, its nite and in nite elementary divisors, and its left and right minimal indices are prescribed. These conditions hold for arbitrary in nite elds and are determined mainly by the \index sum theorem", which is a fundamental relationship between the rank, the degree, the sum of all partial multiplicities, and the sum of all minimal indices of any matrix polynomial. The proof developed for the existence of such polynomial is constructive and, therefore, solves a very general inverse problem for matrix polynomials with prescribed complete eigenstructure. This result allows us to x the problem of the existence of (l)-ifications of a given matrix polynomial, as well as to determine all their possible sizes and eigenstructures. This research was partially supported by the Ministerio de Economía y Competitividad of Spain through grant MTM-2012-32542 and by the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. Publicado

New results on the patterns of linearly independent rows and columns among the blocks of a symplectic matrix are presented. These results are combined with the block structure of the inverse of a symplectic matrix, together with some properties of Schur complements, to give a new and elementary proof that the determinant of any symplectic matrix is +1. The new proof is valid for any field. Information on the zero patterns compatible with the symplectic structure is also presented.

A singular matrix A may have more than one LU factorizations. In this work the set of all LU factorizations of A is explicitly described when the lower triangular matrix L is nonsingular. To this purpose, a canonical form of A under left multiplication by unit lower triangular matrices is introduced. This canonical form allows us to characterize the matrices that have an LU factorization and to parametrize all possible LU factorizations. Formulae in terms of quotient of minors of A are presented for the entries of this canonical form.

The concept of linearization is fundamental for theory, applications, and spectral computations related to matrix polynomials. However, recent research on several important classes of structured matrix polynomials arising in applications has revealed that the strategy of using linearizations to develop structure-preserving numerical algorithms that compute the eigenvalues of structured matrix polynomials can be too restrictive, because some structured polynomials do not have any linearization with the same structure. This phenomenon strongly suggests that linearizations should sometimes be replaced by other low degree matrix polynomials in applied numerical computations. Motivated by this fact, we introduce equivalence relations that allow the possibility of matrix polynomials (with coefficients in an arbitrary field) to be equivalent, with the same spectral structure, but have different sizes and degrees. These equivalence relations are directly modeled on the notion of linearization, and consequently inherit the simplicity, applicability, and most relevant properties of linearizations; simultaneously, though, they are much more flexible in the possible degrees of equivalent polynomials. This flexibility allows us to define in a unified way the notions of quadratification and l-ification, to introduce the concept of companion form of arbitrary degree, and to provide concrete and simple examples of these notions that generalize in a natural and smooth way the classical first and second Frobenius companion forms. The properties of l-ifications are studied in depth; in this process a fundamental result on matrix polynomials, the “Index Sum Theorem”, is recovered and extended to arbitrary fields. Although this result is known in the systems theory literature for real matrix polynomials, it has remained unnoticed by many researchers. It establishes that the sum of the (finite and infinite) partial multiplicities, together with the (left and right) minimal indices of any matrix polynomial is equal to the rank times the degree of the polynomial. The “Index Sum Theorem” turns out to be a key tool for obtaining a number of significant results: on the possible sizes and degrees of l-ifications and companion forms, on the minimal index preservation properties of companion forms of arbitrary degree, as well as on obstructions to the existence of structured companion forms for structured matrix polynomials of even degree. This paper presents many new results, blended together with results already known in the literature but extended here to the most general setting of matrix polynomials of arbitrary sizes and degrees over arbitrary fields. Therefore we have written the paper in an expository and self-contained style that makes it accessible to a wide variety of readers.

In this paper the accuracy of LU factorization of tridiagonal matrices without pivoting is considered. Two types of componentwise condition numbers for the L and U factors of tridiadonal matrices are presented and compared. One type is a condition number with respect to small relative perturbations of each entry of the matrix. The other type is a condition number with respect to small componentwise perturbations of the kind appearing in the backward error analysis of the usual algorithm for the LU factorization. We show that both condition numbers are of similar magnitude. This means that the algorithm is componentwise forward stable, i.e., the forward errors are of similar magnitude to those produced by a componentwise backward stable method. Moreover the presented condition numbers can be computed in O(n) flops, which allows to estimate with low cost the forward errors.

Let A be a matrix and $\lambda_0$ be one of its eigenvalues having g elementary Jordan blocks in the Jordan canonical form of A. We show that for most matrices B satisfying ${\rm rank}\,(B)\leq g$, the Jordan blocks of A+B with eigenvalue $\lambda_0$ are just the $g-{\rm rank}\,(B)$ smallest Jordan blocks of A with eigenvalue $\lambda_0$. The set of matrices for which this behavior does not happen is explicitly characterized through a scalar determinantal equation involving B and some of the $\lambda_0$-eigenvectors of A. Thus, except for a set of zero Lebesgue measure, a low rank perturbation A+B of A destroys for each of its eigenvalues exactly the rank,(B) largest Jordan blocks of A, while the rest remain unchanged.

We propose a new algorithm for the symmetric eigenproblem that computes eigenvalues and eigenvectors with high relative accuracy for the largest class of symmetric, definite and indefinite, matrices known so far. The algorithm is divided into two stages: the first one computes a singular value decomposition (SVD) with high relative accuracy, and the second one obtains eigenvalues and eigenvectors from singular values and vectors. The SVD, used as a first stage, is responsible both for the wide applicability of the algorithm and for being able to use only orthogonal transformations, unlike previous algorithms in the literature. Theory, a complete error analysis, and numerical experiments are presented.

New perturbation theorems are proved for simultaneous bases of singular subspaces of real matrices. These results improve the absolute bounds previously obtained in [6] for general (complex) matrices. Unlike previous results, which are valid only for the Frobenius norm, the new bounds, as well as those in [6] for complex matrices, are extended to any unitarily invariant matrix norm. The bounds are complemented with numerical experiments which show their relevance for the algorithms computing the singular value decomposition. Additionally, the differential calculus approach employed allows to easily prove new sin Θ perturbation theorems for singular subspaces which deal independently with left and right singular subspaces.

The proceeding at: 6th Conference on Structured Numerical Linear and Multilinear Algebra: Analysis, Algorithms and Applications (SLA 2014), took place at 2014, Septembe 8-12, in Kalamata (Grece), Computing roots of scalar polynomials as the eigenvalues of Frobenius companion matrices using backward stable eigenvalue algorithms is a classical approach. The introduction of new families of companion matrices allows for the use of other matrices in the root-finding problem. In this paper, we analyze the backward stability of polynomial root-finding algorithms via Fiedler companion matrices. In other words, given a polynomial p(z), the question is to determine whether the whole set of computed eigenvalues of the companion matrix, obtained with a backward stable algorithm for the standard eigenvalue problem, are the set of roots of a nearby polynomial or not. We show that, if the coefficients of p(z) are bounded in absolute value by a moderate number, then algorithms for polynomial root-finding using Fiedler matrices are backward stable, and Fiedler matrices are as good as the Frobenius companion matrices. This allows us to use Fiedler companion matrices with favorable structures in the polynomial root-finding problem. However, when some of the coefficients of the polynomial are large, Fiedler companion matrices may produce larger backward errors than Frobenius companion matrices, although in this case neither Frobenius nor Fiedler matrices lead to backward stable computations. To prove this we obtain explicit expressions for the change, to first order, of the characteristic polynomial coefficients of Fielder matrices under small perturbations. We show that, for all Fiedler matrices except the Frobenius ones, this change involves quadratic terms in the coefficients of the characteristic polynomial of the original matrix, while for the Frobenius matrices it only involves linear terms. We present extensive numerical experiments that support these theoretical results. The effect of balancing these matrices is also investigated. This work has been supported by the Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542 Publicado

Several matrix norms of the classical Frobenius companion matrices of a monic polynomial p(z) have been used in the literature to obtain simple lower and upper bounds on the absolute values of the roots lambda of p(z). Recently, M. Fiedler (2003) [9] has introduced a new family of companion matrices of p(z) that has received considerable attention and it is natural to investigate if matrix norms of Fiedler companion matrices may be used to obtain new and sharper lower and upper bounds on vertical bar lambda vertical bar. The development of such bounds requires first to know simple expressions for some relevant matrix norms of Fiedler matrices and we obtain them in the case of the 1- and infinity-matrix norms. With these expressions at hand, we will show that norms of Fiedler matrices produce many new bounds, but that none of them improves significatively the classical bounds obtained from the Frobenius companion matrices. However, we will prove that if the norms of the inverses of Fiedler matrices are used, then another family of new bounds on vertical bar lambda vertical bar is obtained and some of the bounds in this family improve significatively the bounds coming from the Frobenius companion matrices for certain polynomials. This work has been supported by the Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542.

This work introduces a new perturbation bound for the L factor of the LDU factorization of (row) diagonally dominant matrices computed via the column diagonal dominance pivoting strategy. This strategy yields L and U factors which are always well-conditioned and, so, the LDU factorization is guaranteed to be a rank-revealing decomposition. The new bound together with those for the D and U factors in [F. M. Dopico and P. Koev, Numer. Math., 119 (2011), pp. 337– 371] establish that if diagonally dominant matrices are parameterized via their diagonally dominant parts and off-diagonal entries, then tiny relative componentwise perturbations of these parameters produce tiny relative normwise variations of L and U and tiny relative entrywise variations of D when column diagonal dominance pivoting is used. These results will allow us to prove in a follow-up work that such perturbations also lead to strong perturbation bounds for many other problems involving diagonally dominant matrices. Research supported in part by Ministerio de Economía y Competitividad of Spain under grant MTM2012-32542. Publicado

The solution of a system of linear equations is by far the most important problem in Applied Mathematics. It is important both in itself and because it is an intermediate step in many other important problems. Gaussian elimination is nowadays the standard method for solving this problem numerically on a computer and it was the first numerical algorithm to be subjected to rounding error analysis. In 1948, Alan Turing published a remarkable paper on this topic: “Rounding-off errors in matrix processes” (Quart. J. Mech. Appl. Math. 1, pp. 287-308). In this paper, Turing formulated Gaussian elimination as the matrix LU factorization and introduced the “condition number of a matrix”, both of them fundamental notions of modern Numerical Analysis. In addition, Turing presented an error analysis of Gaussian elimination for general matrices that deeply influenced the spirit of the definitive analysis developed by James Wilkinson in 1961. Alan Turing’s work on Gaussian elimination appears in a fascinating period for modern Numerical Analysis. Other giants of Mathematics, as John von Neumann, Herman Goldstine, and Harold Hotelling were also working in the mid-1940s on Gaussian elimination. The goal of these researchers was to find an efficient and reliable method for solving systems of linear equations in modern “automatic computers”. At that time, it was not clear at all whether Gaussian elimination was a right choice or not. The purpose of this paper is to revise, at an introductory level, the contributions of Alan Turing and other authors to the error analysis of Gaussian elimination, the historical context of these contributions, and their influence on modern Numerical Analysis., La resolución de sistemas de ecuaciones lineales es sin duda el problema más importante en Matemática Aplicada. Es importante en sí mismo y también porque es un paso intermedio en la resolución de muchos otros problemas de gran relevancia. La eliminación Gaussiana es hoy en día el método estándar para resolver este problema en un ordenador y, además, fue el primer algoritmo numérico para el que se realizó un análisis de errores de redondeo. En 1948, Alan Turing publicó un artículo de gran relevancia sobre este tema: “Rounding-off errors in matrix processes” (Quart. J. Mech. Appl. Math. 1, pp. 287-308). En este artículo, Turing formuló la eliminación Gaussiana en términos de la factorización LU de una matriz e introdujo la noción de número de condición de una matriz, que son dos de las nociones más fundamentales del Análisis Numérico moderno. Además, Turing presentó un análisis de errores de la eliminación Gaussiana para matrices generales que influyó profundamente en el espíritu del análisis de errores definitivo desarrollado por Wilkinson en 1961. El trabajo de Alan Turing sobre la eliminación Gaussiana aparece en un periodo fascinante del Análisis Numérico moderno. Otros gigantes de las matemáticas como John von Neumann, Herman Goldstine y Harold Hotelling también realizaron investigaciones sobre la eliminación Gaussiana en la década de 1940-50. El objetivo de estos investigadores era encontrar un método eficiente y fiable para resolver sistemas de ecuaciones lineales en los ordenadores modernos que estaban desarrollándose por entonces. En aquella época, no estaba claro en absoluto si utilizar la eliminación Gaussiana era una elección adecuada o no. El propósito de este artículo es revisar, a nivel básico, las contribuciones realizadas por Alan Turing y otros investigadores al análisis de errores de la eliminación Gaussiana, el contexto histórico de esas contribuciones y su influencia en el Análisis Numérico moderno.

We present a Weyl-type relative bound for eigenvalues of Hermitian perturbations A+E of (not necessarily definite) Hermitian matrices A. This bound, given in function of the quantity η=∥A−1/2EA−1/2∥2, that was already known in the definite case, is shown to be valid as well in the indefinite case. We also extend to the indefinite case relative eigenvector bounds which depend on the same quantity η. As a consequence, new relative perturbation bounds for singular values and vectors are also obtained. Using matrix differential calculus techniques we obtain for eigenvalues a sharper, first-order bound involving the logarithm matrix function, which is smaller than η not only for small E, as expected, but for any perturbation.

New perturbation theorems for bases of singular subspaces are proved. These theorems complement the known sin Θ theorems for singular subspace perturbations, taking into account a kind of sensitivity of singular vectors discarded by previous theorems. Furthermore these results guarantee that high relative accuracy algorithms for the SVD are able to compute reliably simultaneous bases of left and right singular subspaces.

We solve the matrix equation XA+AX� = 0, where A 2 Cn×n is an arbitrary given square matrix, and we compute the dimension of its solution space. This dimension coincides with the codimension of the tangent space of thecongruence orbit of A. Hence, we also obtain the (real) dimension ofcongruence orbits in C n×n . As an application, we determine the generic canonical structure forcongruence in C n×n and also the generic Kronecker canonical form ofpalindromic pencils A + �A � .

A standard way of dealing with a regular matrix polynomial P (λ) is to convert it into an equivalent matrix pencil - a process known as linearization. Two vector spaces of pencils L1(P ) and L2(P ) that generalize the first and second companion forms have recently been introduced by Mackey, Mackey, Mehl and Mehrmann. Almost all of these pencils are linearizations for P (λ )w hen P is regular. The goal of this work is to show that most of the pencils in L1(P )a ndL2(P )a re stil l linearizations when P (λ) is a singular square matrix polynomial, and that these linearizations can be used to obtain the complete eigenstructure of P (λ), comprised not only of the finite and infinite eigenvalues, but also for singular polynomials of the left and right minimal indices and minimal bases. We show explicitly how to recover the minimal indices and bases of the polynomial P (λ )f rom the minimalindices and bases of l in L1(P )a ndL2(P ). As a consequence of the recovery formulae for minimal indices, we prove that the vector space DL(P )= L1(P ) ∩ L2(P )w il l never contain any linearization for a square singular polynomial P (λ). Finally, the results are extended to other linearizations of singular polynomials defined in terms of more general polynomial bases.

A standard way of dealing with matrixpolynomial eigenvalue problems is to use linearizations. Byers, Mehrmann and Xu have recently defined and studied linearizations of dimen- sions smaller than the classical ones. In this paper, lower bounds are provided for the dimensions of linearizations and strong linearizations of a given m × n matrixpolynomial, and particular lineariza- tions are constructed for which these bounds are attained. It is also proven that strong linearizations of an n × n regular matrixpolynomial of degreemust have dimension n� × n� .

First order perturbation theory for eigenvalues of arbitrary matrices is systematically developed in all its generality with the aid of the Newton diagram, an elementary geometric construction first proposed by Isaac Newton. In its simplest form, a square matrix A with known Jordan canonical form is linearly perturbed to A(e) = A + e B for an arbitrary perturbation matrix B, and one is interested in the leading term in the e-expansion of the eigenvalues of A(e). The perturbation of singular values and of generalized eigenvalues is also covered.

Let A ( λ ) be a complex regular matrix polynomial of degree l with g elementary divisors corresponding to the finite eigenvalue λ 0 . We show that for most complex matrix polynomials B ( λ ) with degree at most l satisfying rank B ( λ 0 ) g the perturbed polynomial ( A + B ) ( λ ) has exactly g - rank B ( λ 0 ) elementary divisors corresponding to λ 0 , and we determine their degrees. If rank B ( λ 0 ) + rank ( B ( λ ) - B ( λ 0 ) ) does not exceed the number of λ 0 -elementary divisors of A ( λ ) with degree greater than 1, then the λ 0 -elementary divisors of ( A + B ) ( λ ) are the g - rank B ( λ 0 ) - rank ( B ( λ ) - B ( λ 0 ) ) elementary divisors of A ( λ ) corresponding to λ 0 with smallest degree, together with rank ( B ( λ ) - B ( λ 0 ) ) linear λ 0 -elementary divisors. Otherwise, the degree of all the λ 0 -elementary divisors of ( A + B ) ( λ ) is one. This behavior happens for any matrix polynomial B ( λ ) except those in a proper algebraic submanifold in the set of matrix polynomials of degree at most l . If A ( λ ) has an infinite eigenvalue, the corresponding result follows from considering the zero eigenvalue of the perturbed dual polynomial.

The K -Orthogonal group of an n -by- n matrix K is defined as the set of nonsingular n -by- n matrices A satisfying A T KA = K , where the superscript T denotes transposition. These form a group under matrix multiplication. It is well-known that if K is skew-symmetric and nonsingular the determinant of every element of the K -Orthogonal group is +1, i.e., the determinant of any symplectic matrix is +1. We present necessary and sufficient conditions on a real or complex matrix K so that all elements of the K -Orthogonal group have determinant +1. These necessary and sufficient conditions can be simply stated in terms of the symmetric and skew-symmetric parts of K , denoted by K s and K w respectively, as follows: the determinant of every element in the K -Orthogonal group is +1 if and only if the matrix pencil K w - λ K s is regular and the matrix ( K w - λ 0 K s ) - 1 K w has no Jordan blocks associated to the zero eigenvalue with odd dimension, where λ 0 is any number such that det ( K w - λ 0 K s ) ≠ 0 .

We establish necessary and sufficient conditions, in the language of bidiagonal decompositions, for a matrix V to be an eigenvector matrix of a totally positive matrix. Namely, this is the case if and only if V and V - T are lowerly totally positive. These conditions translate into easy positivity requirements on the parameters in the bidiagonal decompositions of V and V - T . Using these decompositions we give elementary proofs of the oscillating properties of V. In particular, the fact that the jth column of V has j - 1 changes of sign. Our new results include the fact that the Q matrix in a QR decomposition of a totally positive matrix belongs to the above class (and thus has the same oscillating properties).

The development of fast algorithms to perform computations with quasiseparable matrices has received a lot of attention in the last decade. Many different algorithms have been presented by several research groups all over the world. Despite this intense activity, to the best of our knowledge, there is no rounding error analysis published for these fast algorithms. In this paper, we present error analyses for two fast solvers of quasiseparable linear systems when they are applied on order one quasiseparable matrices that include the diagonal in the lower triangular rank structure. Both solvers are based on computing first the QR factorization of the coefficient matrix, and their error analyses require novel structured techniques for proving rigorously that only one of the considered algorithms is backward stable, while the other one is not. Two fundamental consequences of this work are: (i) users should employ with caution fast algorithms for quasiseparable matrices since they may be unstable; and (ii) a lot of work has to be done to identify which fast algorithms for quasiseparable matrices are backward stable among the large family available in the literature.

In this paper, the matrix equation AX + X⋆B = C is considered, where the matrices A and B have sizes m × n and n × m, respectively, the size of the unknown X is n × m, and the operator (·) ⋆ denotes either the transpose or the conjugate transpose of a matrix. In the first part of the paper, necessary and sufficient conditions for the existence and uniqueness of solutions are reviewed. These conditions were obtained previously by Wimmer (H.K. Wimmer. Roth's theorems for matrix equations with symmetry constraints. Linear Algebra Appl., 199:357- 362, 1994.), by Byers and Kressner (R. Byers and D. Kressner. Structured condition numbers for invariant subspaces. SIAM J. Matrix Anal. Appl., 28:326-347, 2006.), and by Kressner, Schroder and Watkins (D. Kressner, C. Schroder, and D.S. Watkins. Implicit QR algorithms for palindromic and even eigenvalue problems. Numer. Algorithms, 51:209-238, 2009.). This review generalizes to fields of characteristic different from two the existence condition that Wimmer originally proved for the complex field. In the second part, an algorithm is developed, in the real or complex square case m = n, to solve the equation in O(n3) flops when the solution is unique. This algorithm is based on the generalized Schur decomposition of the matrix pencil A λB ⋆ . The equation AX + X ⋆ B = C is connected with palindromic eigenvalue problems and, as a consequence, the square complex case has attracted recently the attention of several authors.