21
$\begingroup$

Before beginning, I should note some similarities to the question: Building matrices from eigenvalues . However, I have a different objective.

The Setup

When writing problems for an introductory linear algebra course, a generic question would be

Find the eigenvalues of $A= \begin{bmatrix} \dots \end{bmatrix}$.

From an instructor perspective, it is generally desirable that the computation be reasonably straightforward (e.g., not tasking students with finding roots of an irreducible quintic). Furthermore, the goal of the question is whether students can correctly find the characteristic polynomial and solve for the roots, rather than the ability to carefully add numerous fractions. As such, matrices $A$ with integer entries are generally preferable, perhaps along with a bias towards positive entries that aren't too large. However, we don't want to make the problem too easy. For example, tasking students with finding the eigenvalues of a diagonal/triangular matrix doesn't make for a particularly good question (unless it is specifically a question of recognizing this property).

As such, it is probably best to write such a question by starting with the eigenvalues and working backwards to generate a matrix $A$ with those eigenvalues.

These thoughts lead me to an (admittedly vague) definition:

A "nifty matrix" $A$ should

  1. Have a given set of eigenvalues $\{\lambda_1, \dots, \lambda_n\}$.

  2. Contain only non-zero integers: $A = (a_{ij}) \in \{\mathbb{Z}\setminus\{0\}\}^{n \times n}$

Note that our conditions necessitate that the eigenvalues be algebraic integers and that the list of eigenvalues must contain all of the Galois conjugates.

For example,

\[ D= \begin{bmatrix} 3 & 0 \\ 0 & 2 \end{bmatrix}, \quad T= \begin{bmatrix} 3 & 7 \\ 0 & 2 \end{bmatrix}, \quad \text{ and } A=\begin{bmatrix} 1 & 1 \\ -2 & 4 \end{bmatrix} \] all have the same eigenvalues, but only $A$ is "nifty matrix" for the eigenvalues $\{3,2\}$. Similarly, $$A= \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}$$ is a "nifty matrix" for the eigenvalues $\lambda_\pm = \frac{3 \pm \sqrt{5}}{2}$.

The Goal

Imagine that you're stuck in a textbook factory and need to write hundreds of "compute the eigenvalues" problems. How would you set about your task? Since you are picking the eigenvalues at the start, you can also control the characteristic and minimal polynomials of $A$, $\chi_A$ and $\mu_A$.

The way I envision this working is a function / algorithm that gives a (perhaps non-unique) mapping

\[{\text{eigenvalues & min. or char. poly} } \longrightarrow \text{nifty matrix}. \]

A simple approach

  1. Start with a list of integer eigenvalues.

  2. Form a diagonal matrix (or Jordan block matrix or upper-triangular matrix) $M$ that has the desired eigenvalues.

  3. Build a matrix $P$ by doing some row operations on the identity matrix, without rescaling rows or adding non-integer copies of rows. By Cramer's rule, $P^{-1}$ will only have integer entries as well.

  4. Form $A= P M P^{-1}$. See how we did. Keep trying different $P$ matrices until something works.

A slightly more sophisticated approach.

This approach has the benefit of starting with the characteristic polynomial, which allows you to generate nifty matrices for eigenvalues that aren't necessarily integers (unlike the above approach).

  1. Pick a suitable characteristic polynomial $\chi$ and minimal polynomial $\mu$, each with integer coefficients.

  2. Build a matrix $C$ that will be the rational canonical form of $A$ using the characteristic polynomial and minimal polynomial. Note that $C$ will have integer entries.

  3. Use our trick from the previous algorithm: $A=P C P^{-1}$ where $\det(P)= \pm 1$. See how we did. Keep trying different $P$ matrices until something works.

The Question

Is there a better way? Note that both of these algorithms are ill-defined--how do we find a $P$ that ensures $A$ has no zero entries?

As an extension of this problem, suppose we defined a super nifty matrix to be a nifty matrix that minimizes $f(A) = \max_{i,j} \{|a_{ij|} \}$ over all similar nifty matrices? How could we find a (probably non-unique) minimizer? What if we minimized with respect to $g(A) = \sum_{i,j} |a_{ij}|$ or any other suitable norm on the entries?

What if we decided that negative numbers are too messy and wanted $A=(a_{ij}) \in \mathbb{N}^{n\times n}$? What conditions would this impose on the eigenvalues and our algorithms?

Edited to Add:

I should note that such "nifty matrices" truly aren't nice problems, outside of the $2 \times 2$ case. This is part of why I didn't call them "nice matrices," but rather "nifty" as in "Hey! This messy looking matrix of integers has my desired eigenvalues/ characteristic polynomial! Isn't that nifty?!" I am primarily interested in this problem as a mathematical construct; generating a clever linear algebra problem is only a motivating idea.

For another, perhaps more "realistic" motivation, you can recast the problem as:

Given a list of $n$ suitable eigenvalues, is it possible to created a complete graph on $n$ vertices such that each edge has a non-zero (possibly negative) integer weight and the weighted transition matrix has the desired eigenvalues? What is the "simplest" such graph? How can you algorithmically construct this graph / weighted transition matrix?

$\endgroup$
  • $\begingroup$ This is a cool question but in practice, if $n > 3$, the factory worker actually wants to do the opposite of what you describe because the calculation of the characteristic polynomial itself becomes a nightmare. For example, you might need to generate some "find the Jordan form and a Jordan basis" exercises and if the Jordan form is interesting enough, you actually want to generate matrices with as many zeros as possible without making it trivial so that the students actually manage to find the characteristic polynomial without performing an absurd amount of calculations. $\endgroup$ – levap Apr 6 '17 at 10:14
  • $\begingroup$ @levap Absolutely! I may have initially wanted to phrase it as "nice matrices," but decided that they really aren't nice =) I settled on calling them "nifty" for this post as in "Hey! This messy looking matrix of integers has my desired eigenvalues/ characteristic polynomial! Isn't that nifty?!" Agreed that for $n>3$ the motivation of the original problem starts to break down, but I think it's an intriguing thought in and of itself. $\endgroup$ – erfink Apr 6 '17 at 10:16
  • $\begingroup$ For "step 3" of your simple approach, you might want to look up ways to generate random unimodular matrices. $\endgroup$ – J. M. is a poor mathematician Apr 6 '17 at 11:30
  • $\begingroup$ @J.M.isn'tamathematician good tip! The algorithms I seem to be finding are still "random", and we are still stuck with the issue of non-deterministically trying different $P$ until we get a suitable $A=P M P^{-1}$. $\endgroup$ – erfink Apr 6 '17 at 17:54
  • $\begingroup$ Algebraic number theory may give you some tools, but I'm not sure. $\endgroup$ – Jyrki Lahtonen Apr 6 '17 at 18:22
2
$\begingroup$

A possible solution looks as follows. The idea is that we start with a diagonal matrix and then alter the matrix without changing its characteristic polynomial.

Consider the following example. We start with the matrix $$ \begin{pmatrix} 3 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{pmatrix} \,, $$ which obviously has the eigenvalues $1$, $2$, and $3$. Its characteristic polynomial is given by $$ \det \begin{pmatrix} 3 - t & 0 & 0\\ 0 & 1 - t & 0 \\ 0 & 0 & 2 - t \end{pmatrix} \,. $$ The determinant does not change if we add a multiple of one row of the matrix to another row. For example, let us add two times the first row to the second row. We obtain that $$ \det \begin{pmatrix} 3 - t & 0 & 0\\ 6 - 2t & 1 - t & 0 \\ 0 & 0 & 2 - t \end{pmatrix} $$ is still the same polynomial as before. The problem, however, is that this is not the characteristic polynomial of the matrix where $t=0$, because the variable $t$ appears in an off-diagonal entry. We can eliminate this $t$, by adding a multiple of a suitable column to another column. In this example, we can add $(-2)$ times the second column to the first one. We obtain that $$ \det \begin{pmatrix} 3 - t & 0 & 0\\ 4 & 1 - t & 0 \\ 0 & 0 & 2 - t \end{pmatrix} $$ is still the same polynomial, and we see that this is the characteristic polynomial of the matrix $$ \det \begin{pmatrix} 3 & 0 & 0\\ 4 & 1 & 0 \\ 0 & 0 & 2 \end{pmatrix} \,. $$ This procedure can be repeated until a satisfying result is reached. In summary the procedure is

  1. Choose a diagonal matrix having the desired eigenvalues (from $\mathbb{Z}$) on the diagonal.
  2. Pick $i \not= j$, and $a \in \mathbb{Z}$.
  3. Add $a$ times the $j$th row to the $i$th row.
  4. Add $-a$ times the $i$th column to the $j$th column.
  5. Repeat from step 2. until satisfied.

This procedure works, as long as not all eigenvalues are identical.

I turned this idea into a Python script, which can be found at github. The script might generate matrices that sometimes have zeros in random places, however, this could be fixed using more sophisticated program logic.

$\endgroup$
  • $\begingroup$ Certainly seems like a good start. However, what if the eigenvalues are algebraic integers not belonging to $\mathbb{Z}$? E.g. $\begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}$ has eigenvalues of $\lambda= \frac{ 3 \pm \sqrt{5}}{2}$? $\endgroup$ – erfink Aug 12 '17 at 1:43
  • $\begingroup$ I assumed that the eigenvalues are supposed to be integers. That is true. $\endgroup$ – H. Rittich Aug 12 '17 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.