MATLAB: How to solve a rank deficient Sylvester’s Equation with linear constraints

equationsfactorizationleastlyapunovMATLABqrsquaressylvester

I have the following systems of linear equations and need to solve for the N-by-N matrix X:
AX + XB = F
CX = D
The known matrices A, B and F are N-by-N matrices and C and D are M-by-N matrices where M > N.  A and/or B may be singular.  How can I solve this system for X?

Best Answer

This problem can be solved in the least-squares sense.  Let C = QR be the QR-factorization of C.  We can manipulate the equations to yield a single Sylvester Equation that can be solved using MATLAB's "sylvester" function.
By left multiplying CX = D by Q' and adding it to AX + XB = F we have
(R + A) X + XB = F + Q'D
Which is a Sylvester equation that can be solved if R+A shares no eigenvalues with B.  Here is a simple example that validates this method.  A and B are 8-by-8 matrices and C and D are 12-by-8 matrices all of rank 4.  The matrix T is an 8-by-8 matrix of arbitrary rank and F = 0.
>> A = randn(8, 4)*randn(4, 8); % rank 4 random matrix
>> T = randn(8); % random 8-by-8 matrix
>> B = -inv(T)*A*T; % formulate B matrix such that T is solution
>> C = randn(12, 4)*randn(4, 8); % rank 4 12-by-8 random matrix
>> D = C*T; % formulate D such that T is solution matrix
>> [Q,R] = qr(C, 0);
>> At = (R+A);
>> Tt = sylvester(At, B, Q'*D);
>> norm(T-Tt)
ans =
   2.4474e-13
Related Question