Blog > An Introduction to Linear Preserver Problems

An Introduction to Linear Preserver Problems

August 5th, 2010

The theory of linear preserver problems deals with characterizing linear (complex) matrix-valued maps that preserve certain properties of the matrices they act on. For example, some of the most famous linear preserver problems ask what a map must look like if it preserves invertibility or the determinant of matrices. Today I will focus on introducing some of the basic linear preserver problems that got the field off the ground – in the near future I will explore linear preserver problems dealing with various families of norms and linear preserver problems that are actively used today in quantum information theory. In the meantime, the interested reader can find a more thorough introduction to common linear preserver problems in [1,2].

Suppose Φ : Mn → Mn (where Mn is the set of n×n complex matrices) is a linear map. It is well-known that any such map can be written in the form

where {Ai}, {Bi} ⊂ Mn are families of matrices (sometimes referred to as the left and right generalized Choi-Kraus operators of Φ (phew!)). But what if we make the additional restrictions that Φ is an invertible map and Φ(X) is nonsingular whenever X ∈ Mn is nonsingular? The problem of characterizing maps of this type (which are sometimes called invertibility-preserving maps) is one of the first linear preserver problems that was solved, and it turns out that if Φ is invertibility-preserving then either Φ or T ○ Φ (where T represents the matrix transpose map) can be written with just a single pair of Choi-Kraus operators:

Theorem 1. [3] Let Φ : Mn → Mn be an invertible linear map. Then Φ(X) is nonsingular whenever X ∈ Mn is nonsingular if and only if there exist M, N ∈ Mn with det(MN) ≠ 0 such that

In addition to being interesting in its own right, Theorem 1 serves as a starting point that allows for the simple derivation of several related results.

Determinant-Preserving Maps

For example, suppose Φ is a linear map such that det(Φ(X)) = det(X) for all X ∈ Mn. We will now find the form that maps of this type (called determinant-preserving maps) have using Theorem 1. In order to use Theorem 1 though, we must first show that Φ is invertible.

We prove that Φ is invertible by contradiction. Suppose there exists X ≠ 0 such that Φ(X) = 0. Then because Φ preserves determinants, it must be the case that X is singular. Then there exists a singular Y ∈ Mn such that X + Y is nonsingular. It follows that 0 ≠ det(X + Y) = det(Φ(X + Y)) = det(0 + Φ(Y)) = det(Y) = 0, a contradiction. Thus it must be the case that X = 0 and so Φ is invertible.

Furthermore, any map that preserves determinants must preserve the set of nonsingular matrices because X is nonsingular if and only if det(X) ≠ 0. It follows from Theorem 1 that for any determinant-preserving map Φ there must exist M, N ∈ Mn with det(MN) ≠ 0 such that either Φ(X) = MXN or Φ(X) = MXTN. However, in this case we have det(X) = det(Φ(X)) = det(MXN) = det(MN)det(X) for all X ∈ Mn, so det(MN) = 1. Conversely, it is not difficult (an exercise left to the interested reader) to show that any map of this form with det(MN) = 1 must be determinant-preserving. What we have proved is the following result, originally due to Frobenius [4]:

Theorem 2. Let Φ : Mn → Mn be a linear map. Then det(Φ(X)) = det(X) for all X ∈ Mn if and only if there exist M, N ∈ Mn with det(MN) = 1 such that

Spectrum-Preserving Maps

The final linear preserver problem that we will consider right now is the problem of characterizing linear maps Φ such that the eigenvalues (counting multiplicities) of Φ(X) are the same as the eigenvalues of X for all X ∈ Mn (such maps are sometimes called spectrum-preserving maps). Certainly any map that is spectrum-preserving must also be determinant-preserving (since the determinant of a matrix is just the product of its eigenvalues), so by Theorem 2 there exist M, N ∈ Mn with det(MN) = 1 such that either Φ(X) = MXN or Φ(X) = MXTN.

Now note that any map that preserves eigenvalues must also preserve trace (since the trace is just the sum of the matrix’s eigenvalues) and so we have Tr(X) = Tr(Φ(X)) = Tr(MXN) = Tr(NMX) for all X ∈ Mn. This implies that Tr((I – NM)X) = 0 for all X ∈ Mn, so we have NM = I (i.e., M = N-1). Conversely, it is simple (another exercise left for the interested reader) to show that any map of this form with M = N-1 must be spectrum-preserving. What we have proved is the following characterization of maps that preserve eigenvalues:

Theorem 3. Let Φ : Mn → Mn be a linear map. Then Φ is spectrum-preserving if and only if det(Φ(X)) = det(X) and Tr(Φ(X)) = Tr(X) for all X ∈ Mn if and only if there exists a nonsingular N ∈ Mn such that

References:

  1. C. K. Li, S. Pierce, Linear preserver problems. The American Mathematical Monthly 108, 591–605 (2001).
  2. C. K. Li, N. K. Tsing, Linear preserver problems: A brief introduction and some special techniques. Linear Algebra and its Applications 162164, 217–235 (1992).
  3. J. Dieudonne, Sur une generalisation du groupe orthogonal a quatre variables. Arch. Math. 1,
    282–287 (1949).
  4. G. Frobenius, Uber die Darstellung der endlichen Gruppen durch Linear Substitutionen. Sitzungsber
    Deutsch. Akad. Wiss. Berlin 994–1015 (1897).
  1. August 5th, 2010 at 22:48 | #1

    Hi Nathaniel,

    Zach Harris here. I went searching for “determinant preserving linear maps” and found your blog entry, which it looks like you just posted today. How convenient! Although I haven’t continued on in academia, I have a nagging interest to try to tie up the loose ends of my research from the math PhD I finished a year ago.

    One question I have is: what is known about linear invertibility-, determinant-, and spectrum-preservers between (say, complex) matrix subspaces (which, of course, allows for more freedom than is allowed for from all of M_n to M_n)? For example, the map from (a 0; 0 b) to (a a; 0 b) preserves the eigenvalues, but cannot be expressed in the form of Theorem 3 from your post (because, for example, the range contains non-diagonalizable elements).

    More to the point, what I’m really interested in is the following. Clearly there are linear matrix subspaces which contain all real eigenvalues (just like symmetric subspaces do) but which are not themselves “simultaneously symmetrizable”—for example the space (a a; 0 b) contains all real eigenvalues but there is no matrix N such that N^{-1}(a a; 0 b)N is a symmetric matrix subspace. However, there IS a linear spectrum-preserving map from (a a; 0 b) onto a symmetric matrix subspace, say (a 0; 0 b) again. The question is, when is it possible to find such a linear spectrum-preserving map from a real eigenvalue matrix subspace onto a symmetric subspace?

    In one chapter of my dissertation I explored these questions to a limited extent (it wasn’t my main point), summarized some known results and provided a couple counter-examples of my own, but there are questions still left open. Since you blogged about Linear Preserver Problems I was wondering if you would have any insight into, or existing knowledge regarding these questions.

    The relevance of all this, at least in the field of optimization that I work in, is the question of whether a large, new class of optimization problems (hyperbolic programming) can be represented as semi-definite programming (SDP) problems for which we already have existing efficient algorithms.

    Zach
    Longmont, CO, USA

  2. August 6th, 2010 at 02:13 | #2

    @Zach Harris – Thanks for taking the time to ask such interesting questions, but unfortunately I don’t have a single useful answer for you. I’m aware of some work that looks at linear preservers in slightly more general settings such as general Hilbert/Banach spaces or linear preservers on fields that aren’t algebraically closed, but I’m not familiar with any work dealing with preservers on matrix subspaces.

    Good luck!

  1. No trackbacks yet.