convert this matrix equation into something numpy can understand

Question

I know how to solve basic linear matrix equations with numpy.

However, I have a matrix A and the equation A^2 + xA + yI = 0, where x and y are not vectors, but rather a scalar. I is the identity matrix, and 0 is the zero matrix of dimensions matching A.

This is a super easy on paper for small matrices (assuming of course that a solution exists), but I'm practicing for a coding interview and will be expected to solve problems like this with python. And maybe the matrix given will be quite large...

Here is a sample matrix A, which results in solutions x=-2, y=1:

np.array([[1,1,0],
          [0,1,0]
          [0,0,1]]

On paper, this is as easy as solving the system of linear equations x = -2 and x+y=-1. The issue I am facing is parsing the equation in its form above to one that is in the form of a system of equations (or alternatively a linear matrix equation of the form Ax = B).

y is also an unknown scalar? So you are trying to find scalars x and y to satisfy the equation? — Warren Weckesser
You say the problem is "super easy on paper for small matrices", but "small" must mean 2x2, because for larger matrices, in general, a solution will not exist. You'll have more equations than unknowns. — Warren Weckesser
@WarrenWeckesser for some sparse matrices, it can work. There will be a repetition of equations, so the total number of unique equations will equal the total number of unknowns. The example I am going off of can be found here: hackerrank.com/challenges/… — rocksNwaves
Can you edit the question so we have all the relevant information here on stackoverflow? — Warren Weckesser

Ami Tavory Ami Tavory · Accepted Answer · 2020-02-22T21:12:18

The issue I am facing is parsing the equation in its form above to one that is in the form of a system of equations (or alternatively a linear matrix equation of the form Ax = B

Say that A has n columns. For a square matrix Q with n columns, let E(Q) be the length-n^2 vector formed by iterating over the entries of Q (say in row-major order).

Then solving for x, y in

A^2 + xA + yI = 0

is equivalent to solving for z in the system

B z = -c

where

z = [x, y] is a length-2 column vector
B is the n^2 X 2 matrix whose columns are E(A) and E(I)
c is E(A^2)

convert this matrix equation into something numpy can understand

1 Answers