In this post, we shall discuss various generalizations of the notion of the spectral radius to a sort of spectral radius for collections of multiple operators, and we shall develop the theory of the -spectral radius . This post consists of the new mathematical research on spectral radii which I will apply to measure the cryptographic security of block cipher round functions with very small key space and small message space. The results that are about the -spectral radii are due to J. Van Name unless otherwise stated while all other results stated are due to others unless otherwise or are standard results in quantum information theory. This post shall be a purely mathematical post, so this post will not contain any cryptography nor will we discuss algorithms that one can use to compute the spectral radii or at least bounds for the spectral radii. I expect for the notion of the -spectral radius to extend to infinite dimensional Hilbert spaces, but no one has formulated such a generalization yet. Future posts about spectral radii will be about the application of spectral radii to cryptography, algorithms, the results of these computations, and possible an -spectral radius for infinite dimensional spaces.

This post includes a large amount of linear algebra and quantum information theory. I recommend the book The Theory of Quantum Information by John Watrous (2018) for information about quantum information theory; most of the facts about linear algebra and quantum information theory that I state but do not prove can be found in The Theory of Quantum Information. I intend for this post to be accessible to people who understand linear algebra but who do not necessarily have much knowledge about functional analysis, quantum information theory, quantum computation, or quantum mechanics.

**Spectral radius**

Suppose that is a complex Banach space that contains an operation that makes into a unital ring. Then we say that is a unital Banach algebra if whenever and if

If , then the spectrum of is the set of all complex numbers where is not invertible. If is a square complex matrix, then is simply the set of all eigenvalues of . The spectrum is always a compact non-empty subset of . Define the spectral radius of to be . The following theorem motivates the spectral radius as a measure of the growth rate of

Theorem: If , then

We have whenever and this sum converges absolutely. On the other hand, diverges whenever . More generally, is the radius of convergence of the power series .

We may generalize the notion of the spectral radius to a spectral radius of multiple operators in several different ways. If is a Banach algebra, , and , then define the -spectral radius as (it is not too hard to show that this limit exists). Observe that when , this definition of does not depend on the choice of norm, and this definition still holds even if we drop the requirement that the norm is sub-multiplicative. Define (this limit exists) . We can also write in terms of the norm for by letting Here, denotes the norm.

If is a ring and , then we say that is jointly nilpotent if for all but finitely many strings .

Basic observations: Suppose that is a Banach algebra and . Let be an invertible element in . Suppose that Let .

- whenever is an invertible element in .
- for each scalar .
- whenever .
- .
- if and only if is jointly nilpotent.

To prove the above fact, we use the fact that if , then

While the spectral radii are distinct important generalizations of the notion of a spectral radius, for this post, we shall be primarily concerned with the spectral radius . For the rest of this post, we shall assume all vector spaces are finite dimensional inner product spaces.

Let be a finite dimensional complex inner product spaces. Let denote the space of all linear operators from to , and let . If , then define a mapping by letting Throughout this post, we shall implicitly use the fact that the operator is similar to

If , then recall that the -Schatten norm of a complex matrix is defined by letting for and If are the singular values of , then . If are real or complex matrices with the same dimensions, then define the Frobenius inner product . Observe that . If then .

The following proposition was originally proven by Ding-Xuan Zhou in the 1998 paper titled The -norm joint spectral radius for even integers.

Proposition: .

Proof: Let be the collection of all positive semidefinite matrices with . Observe that if is positive semidefinite, then if and only if . We will need to use the fact that .

For this proof, the norm on an operator from to shall be the maximum value of such that . We have

=. Q.E.D.

Corollary: If is an even integer, then .

Proposition: Suppose that are positive real numbers with . Then .

Proof: Assume that our matrix norm satisfies the property for all matrices . By applying Holder’s inequality, we perform the following calculations.

Q.E.D.

The above inequality is sharp when since .

Example: If are unitary matrices, then More generally, if are constants, then

Example: Suppose that are matrices. Then

Example: If are matrices, then

**Quantum information theory**

A mapping is said to be positive if is positive semidefinite whenever is positive semidefinite. The mapping is said to be completely positive if is positive whenever is a finite dimensional complex inner product space. The mapping is said to be trace preserving if for each The mapping is said to be unital if A mapping is said to be a quantum channel if is completely positive and trace preserving.

If are complex vector spaces, then there is a unique linear mapping where whenever . This linear mapping is known as the partial trace.

Observation: Suppose that , and . Then

- and

If are finite dimensional complex inner product spaces, then are inner product spaces with the Frobenius norm. In this case, if is a linear mapping, then the adjoint of is the adjoint with respect to the Frobenius norms on and .

Let be finite dimensional complex inner product spaces. Every mapping in is a linear combinational of mappings of the form where Therefore, if , then let be the mapping defined by letting whenever . If , then let be the mapping defined by letting and define by letting We shall sometimes write for and for in order to specify the vector space . Observe that and , and whenever these equations make sense.

The linear operator is similar to the linear operator .

Theorem: Let be finite dimensional complex inner product spaces. Let be a linear mapping. The following are equivalent:

Theorem: Let be finite dimensional complex inner product spaces. Let be a linear mapping. The following are equivalent:

- is completely positive.
- is positive.
- for some and .
- for some finite dimensional complex inner product space and .

Theorem: Let be finite dimensional complex inner product spaces. Let be a linear mapping. Then the operator is trace preserving if and only if its adjoint is unital.

Theorem

1: Let . Then

i. The following are equivalent:

a. is trace preserving.

b.

c. .

ii. The following are equivalent:

a. is unital.

b. .

c. .

2. Let Then

i. The following are equivalent:

a. is trace preserving.

b. .

c. .

ii. The following are equivalent:

a. is unital.

b. .

c. .

Theorem: Suppose that and are linear. The mapping is a quantum channel if and only if is an isometry. The mapping is a quantum channel if and only if .

Example: The completely depolarizing channel is the channel defined by letting . The completely depolarizing channel is unital. If , then let be the -matrix defined by letting where refers to the Kronecker delta function. Then . We shall write in order to specify the space , and we shall write for .

Example: Suppose that is a probability vector. Let be a finite dimensional complex inner product space. Let be unitary operators. Then let be the function where for each . Then we say that is mixed unitary. Every mixed unitary operator is a unital channel, but not every unitary channel is mixed unitary. However, John Watrous has shown that there is a neighborhood of the completely depolarizing channel where if , then is mixed unitary if and only if it is unital.

Example: The complete dephasing channel is the channel defined by letting precisely when for and for . Suppose that are the matrices where for and where the addition in the subscript is taken modulo . Then

Example: The shifted complete dephasing channel is the channel defined by letting precisely when for and for where the addition in the subscripts is taken modulo . Suppose now that are the matrices where for and where the addition in the subscript is taken modulo . Then

Example: The shifted complete dephasing channel is the channel defined by letting precisely when for and for where the addition in the subscripts is taken modulo . Suppose now that are the matrices where for and where the addition in the subscript is taken modulo . Then

Proposition: If is positive and either trace preserving or unital, then .

Proof outline: Since is trace preserving if and only if its adjoint is unital, we only have to prove this result when is trace preserving.

If is positive and trace preserving, then whenever is positive semidefinite, we have . From this fact, one can easily conclude that . Q.E.D.

Proposition: If is positive and whenever is a positive semidefinite matrix with , then has a positive semidefinite eigenvector with non-zero eigenvector.

Proof: Let be the collection of all positive semidefinite operators with . Define a mapping by letting Then by Brouwer’s fixed point theorem, there is some with . Therefore, .

Q.E.D.

Corollary: If is positive and trace preserving, then there is a positive semidefinite with and .

Proposition: If is a positive mapping. If is a positive definite eigenvector, then

Proof: Suppose that is an eigenvalue with and is an eigenvector with . Then there are positive semidefinite with . Therefore, there is some with for all .

For all , we have This is only possible if .

Q.E.D.

**Tensor products**

We will apply the following observations about tensor products and related constructions to the -spectral radius.

Proposition: Suppose that are -complex matrices. Then if and only if there is an -unitary matrix such that for .

Lemma: Suppose that are linear operators. Then if and only if there is a unitary such that .

Lemma: Suppose that are matrices over a field where are of the same dimensions and are of the same dimensions. Let be -matrices over the field . Suppose furthermore that and for . If , then .

Lemma: Suppose that are complex matrices where have the same dimensions, and have the same dimensions. Let be complex -matrices. Suppose that and for and , then

Lemma: Let be finite dimensional complex inner product spaces. Suppose that and are linear mappings. Let be linear mappings. Suppose that and . Then .

Proposition: Let be finite dimensional complex inner product spaces. Let be linear. Let be an orthonormal basis for . Let be linear. Suppose that . Then .

Observation: Let be finite dimensional complex inner product spaces. Suppose that is an orthonormal basis for . Let be linear operators. Suppose that are linear operators and . Let be linear. Then

Proposition: Let be finite dimensional complex inner product spaces. Suppose that are linear mappings. Let be an orthonormal basis for . Let be linear maps. Suppose that . Then .

**-spectral radius.**

Let be the collection of all tuples which are not jointly nilpotent. Suppose that are complex matrices. Then define the -spectral radius of by

By the Cauchy-Schwarz inequality , we know that whenever , and since we know that if , then .

Proposition: Suppose that are complex matrices. Suppose that there is a unitary matrix such that for . Then .

Proof: Let Then is unitary. Suppose now that . Then there are with Now set for , then and . Therefore, , so . We can therefore conclude that

For the reverse inequality, observe that if , then and is unitary, so we can conclude that as well.

Q.E.D.

Corollary: If , then for all .

If is a completely positive superoperator, then define by letting whenever . By the above corollary, the quantity is well-defined. If is a linear operator, then define

Observation: Let be finite dimensional complex inner product spaces with . Let be an orthonormal basis for . Let and let . Let , and let Then the following quantities are equivalent:

- .

Proof outline: By definition 1-3 are equivalent to each other. The equivalence between 1 and 4 follows from the fact that and The equivalence between 4 and 5 follows from the fact that if and , then and The equivalence between 6 and 7 follows from the fact that . The equivalence between 1 and 7 follows from the fact that and

Q.E.D.

We shall soon see how in the above result, each of the suprema can actually be reached, so we can replace each supremum with a maximum.

Proposition: Suppose that are -complex matrices. Suppose furthermore that there is an invertible -complex matrix , a complex number and a unitary matrix such that for . Then .

Proof: It is easy to see that . Furthermore, since , we know that as well. Q.E.D.

Lemma: Suppose that are linear operators. If , then

Proof: We have . Therefore, is similar to , so . We therefore conclude that . Furthermore, we have , so as well.

Q.E.D.

Lemma: Suppose that are linear operators. If , then

Proof: Observe that . Therefore, is similar to , so . We conclude that , and clearly .

Now, since , we know that

. Q.E.D.

**Quantum channels and spectral radii**

Here, we give theorems that interpret the spectral radii in terms of quantum channels.

Let be finite dimensional complex Hilbert spaces. Suppose that is a positive mapping. Suppose that has a positive definite eigenvector with non-zero (necessarily positive) eigenvalue . Then define a positive operator by . Then is unital.

Suppose that is a positive mapping. Suppose that has a positive definite eigenvector with non-zero (necessarily positive) eigenvalue . Then define a mapping by letting . Then is trace preserving and positive. In particular, if is a completely positive, and has a positive definite eigenvector , then is a quantum channel.

We say that a positive operator is pre-unital if has a positive definite eigenvector with non-zero (necessarily positive) eigenvalue . We say that a positive operator is pre-trace preserving if has a positive definite eigenvector with non-zero (necessarily positive) eigenvalue .

We say that a tuple is pre-unital (pre-trace preserving) if is pre-unital (pre-trace preserving). We say that is pre-unital (pre-trace preserving) if is pre-unital (pre-trace preserving).

Proposition: Let be a finite dimensional complex inner product space. Let be a positive operator. The following are equivalent:

- is pre-unital.
- There is some positive definite and non-zero where if , then is unital.
- There is some invertible and non-zero where if , then is unital.

In particular, is the spectral radius of the operator

Proposition: Let be a finite dimensional complex inner product space. Let be a positive operator. The following are equivalent:

- is pre-trace preserving.
- There is some positive definite and non-zero where if , then is trace preserving.
- There is some invertible and non-zero where if , then is trace preserving.

Proposition: Let be finite dimensional complex inner product spaces where is an orthonormal basis for . Let and suppose that . Then the following are equivalent:

- is pre unital.
- There exists some invertible and some where is unital.
- There is some positive definite and some where is unital.
- There exists some invertible and some where is unital.
- There exists some positive definite and some where is unital.

Proposition: Let be finite dimensional complex inner product spaces where has orthonormal basis . Let , and suppose that . Then the following are equivalent:

- is pre-trace preserving.
- There exists some invertible and some where is trace preserving.
- There is some positive definite and some where is trace preserving.
- There exists some invertible and some where is trace-preserving.
- There exists some positive definite and some where is trace-preserving.

Observation: Let be finite dimensional complex vector spaces and let be a subspace of Let be linear operators. Let be a linear operator. Let be positive semidefinite.

- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .

From the following proposition, we can conclude that if , then almost all tuples are both pre-unital and pre-trace preserving.

Proposition: Let be a finite dimensional complex inner product space. Let . Suppose that has no irreducible subspace other than and . Then is both pre-unital and pre-trace preserving.

Theorem: (J. Van Name) Let be finite dimensional complex vector spaces where has orthonormal basis and Let , and suppose that . Suppose that The following quantities are equivalent:

- .
- .
- .
- .
- .
- .

Proof: Observe that is compact, so the maximum actually exists. By similar arguments, one can show that the maximum exists in 3-9. Furthermore, observe that the quantities in 3-9 are all less than or equal to

Suppose that . Then there is some where . Therefore, there is a pre-trace preserving and pre-unital with . Since is pre-trace preserving, there is some and invertible where is trace preserving. In this case, if for , then

Therefore, since

Therefore,

.

Since is pre-unital, there is some and invertible where is unital. Let for . In this case, we have so

Thus as well.

The proofs that are all greater than or equal to are similar to the proofs that .

Q.E.D.

Let be finite dimensional complex Hilbert spaces. Suppose that is a linear operator. Then define the induced trace norm of as , and define the completely bounded trace norm of as . Both the induced trace norm and the completely bounded trace norm are submultiplicative, so whenever .

The proof of following lemma can be found in the 2012 paper ‘Relations for certain symmetric norms and anti-norms before and after partial trace’ by Alexey E. Rastegin.

Lemma: Let be finite dimensional complex inner product spaces. Let be a linear operator. Suppose that . Then . In particular, .

If is a positive and trace preserving map, then . If is a quantum channel, then

Observe that if . Therefore, .

Observation: (J. Van Name) Let be finite dimensional complex Hilbert spaces with and where has orthonormal basis . Let and suppose that is the mapping where . Then the following quantities are equivalent:

There are other similar formulae for , but for the sake of brevity, we shall leave the task of finding other formulae for to the reader.

Observation: whenever are complex matrices, are isometries, and this product makes sense.

Lemma: Suppose that are isometries. Then .

Proof: Observe that whenever is an operator. Therefore, . Q.E.D.

Lemma: Suppose that are isometries. Then .

Proof: Suppose that is an eigenvalue for . Then for some . Therefore, . Now, by the polar decomposition, there is a positive semidefinite and an isometry where . Let . Now, .

Suppose that . Then and . Therefore, . This is only possible if .

Q.E.D.

Theorem: (J. Van Name) Suppose that are finite dimensional complex vector spaces and . Suppose that is pre-trace preserving, and is has no non-trivial invariant subspace. If , then has an invariant subspace and there is a linear bijection and non-zero with for where is the restriction of to the invariant subspace .

Proof: Since are both pre-trace preserving, there are matrices and non-zero complex numbers such that if for , then are quantum channels. Suppose now that . Then

Suppose now that are the same as in the above lemma, and suppose that . Then .

This is only possible if whenever . This happens precisely when . Therefore, we have . We therefore, conclude that . The positive definite matrix is positive definite, so .

Suppose that . Then . Therefore, whenever .

Now, let be the restrictions of .

The mapping is unitary. Here, . Therefore, , so . Therefore, , so

Q.E.D.

Theorem: (J. Van Name) Let be finite dimensional complex inner product spaces. Suppose that are linear operators. Then we can assign the vector spaces bases such that for , we can write the operators as block matrices to get

and

where

i. whenever ,

ii. is square whenever ,

iii. has no non-trivial irreducible subspace whenever ,

iv. whenever

v. is square whenever , and

vi. has no non-trivial irreducible subspace whenever .

Given such a decomposition of into block matrices, the following are equivalent:

- There exists , a complex number and an invertible where and and where for .

Corollary: (J. Van Name) If has no non-trivial invariant subspace, then whenever .

Proof: By the above result, we can choose such that , but by the above result, we know that Q.E.D.

Statement 1 in the following theorem was originally proven by Fedja from MathOverflow, but the proof given is by Joseph Van Name (I was only able to see how quantum channels were related to after reading Fedja’s proof).

Theorem: (J. Van Name) Let be positive integers. Suppose that is a -matrix with real entries whenever . Let be the matrix that can be written as the block matrix

Then

2. For all , the matrices can be chosen such that

3. If and , then for each .

4. Let denote the complete depolarizing channel. Then .

Proof:

If is an -complex matrix, then let be the system of submatrices so that

Let be the collection of all systems where is not nilpotent. Let be the collection of all systems which are pre-trace preserving. Let (resp ) be the collection of all where (resp ).

Suppose that is an -matrix where is a quantum channel. Then

Therefore, . Furthermore, if , then , and this is only possible if .

- Suppose now that Then there is a complex number and an invertible where is a quantum channel. Suppose now that is the matrix with for each . In this case,

. Furthermore, if and , then , so as well. Since is dense in , we conclude that whenever .

2. Let if or , and if and , then let be the matrix where the -th entry is but every other entry is . In this case, we have .

3. We shall now define functions and . Let whenever and where are the eigenvalues of ordered so that Observe that if , then precisely when .

Now suppose that . Then let . Then there is some where if and , then Now select a matrix with . Then . Therefore, there is some and where if is the matrix with for each , then is a quantum channel. Therefore, we have .

Thus, Let be the eigenvalues of ordered such that . Then . Therefore, , so .

We conclude that . Therefore, as , so which means that .

4. Let be the -matrix where all entries in are zero except for the -th entry, and where the -th entry in is . Observe that and if is a -matrix, then . Therefore, , so

Q.E.D.

Let be an inner product space. Then is said to be a frame if there are with for all If , then we say that the frame is a tight frame. In other words, is a tight frame if for all . We observe that is a tight frame precisely when . An equal-norm tight frame is a tight frame where for all .

Lemma: Suppose that is either the field of real or complex numbers. There exists an equal-norm tight frame for the inner product space .

See Corollary 7.1 in the book An Introduction to Finite Tight Frames by Shayne F. D. Waldron for a proof of the above lemma.

Lemma: (Weyl’s inequality) Suppose that is a -matrix with eigenvalues and singular values ordered such that and . Then whenever .

Let be a natural number. Let be the matrices where such that refers to the Kronecker delta function and where the addition is taken modulo . Then Therefore, is the maximum value of where .

Theorem: (J. Van Name) Suppose that

- whenever .

2. If are matrices such that , then for .

3. Suppose are matrices. Then the following are equivalent:

i. is a quantum channel with .

ii. there is an equal-norm tight frame with for and with for where if , then for .

4. There are real -matrices such that is a quantum channel and .

5. Let be the matrices in the above example. Then

Proof:

- Suppose that and is a quantum channel. Then .

Therefore, by the arithmetic-geometric mean inequality, we have

Therefore, if is a complex number, is a complex matrix, and for , then . Therefore, whenever is pre-trace preserving. We conclude that for all by continuity since the pre-trace preserving maps are dense in whenever .

2. If , and is a quantum channel with , then for all which implies that for . By applying continuity, we shall show that if , and , then for .

Let be the collection of all tuples which are pre-trace preserving. Let be the mapping defined by

Let be the mapping where where are the eigenvalues of ordered in such a way so that . Let be the mapping defined by letting

Suppose now that and suppose that . Then for each , there is a neighborhood of where if , then Therefore, select a . Then there is some and invertible where if we set , then is a quantum channel. Now, for , let be the eigenvalues of and suppose that these eigenvalues are ordered in a way so that . Then

Therefore, we conclude that and . We conclude that Therefore, so for .

3. Suppose that is a quantum channel and Then since , there are vectors with for . In this case, Therefore, .

Thus,

Since , we have

This means that there are non-zero constants where for .

Now set, . Then Observe that is an equal-norm tight frame with for all . In this case, if we set so that , then Therefore, we have .

Now suppose that is an equal-norm tight frame with for and with for where if , then for .

Then

Q.E.D.

**Miscellaneous examples**

Here are a few examples of where we give bounds for .

Example: (J. Van Name). Suppose that is completely positive. Then .

Proof: Suppose that are matrices with whenever . Let be -matrices where is a quantum channel and .

In this case, , so is a quantum channel. However, we have

.

Therefore, . Therefore, .

Q.E.D.

For the next example, observe that tensor products behave well with regards to the Frobenius norm. Here, whenever are complex matrices where the formula makes sense. In particular, if are orthogonal, then are also orthogonal.

Example: (J. Van Name) Suppose that are -complex matrices. Then .

Proof: Suppose that are -complex matrices where is a quantum channel and has as an eigenvalue with .

Suppose now that . Then is a quantum channel, and

, and has as an eigenvalue. is maximized subject to when In this case, we have . Therefore, . Q.E.D.

We conjecture that .

Proposition: (J. Van Name) Suppose that is a linear operator. Then

Proof: The mapping is a positive semidefinite sesquilinear form. Therefore, there is a positive semidefinite such that . Since is positive semidefinite, there is a basis for and non-negative with . Now set for . In this case, we have . Now,

whenever . Furthermore,

.

Suppose now that is a quantum channel. Then

. Therefore,

We conclude that Q.E.D.

**Conclusions**

We have seen that there are many different sensible notions of a spectral radius of multiple operators, but in many regards, the -spectral radius seems to be the correct way to generalize the spectral radius to multiple operators, and the -spectral radius seems to be a sensible approximation to the -spectral radius.

While we have produced a few basic results that initially develop the theory of the -spectral radius, computer calculations indicate that the pure mathematical theory of the -spectral radius can be developed much further. In particular, if with , and , then our computer calculations suggest that the linear operator seems to be unique up to simultaneous similarity in most cases, and seems to inherit at least to some extent many of the properties that has including rank, realness, symmetry, self-adjointness, positivity, unitarity, etc. One should therefore consider the operator as an operator obtained by reducing the dimension of the space to obtain the space while preserving the properties of in the best possible way.

The -spectral radius is a mathematical function that should therefore be of interest to pure mathematicians for purely mathematical and aesthetic reasons, but we will apply the -spectral radius to measure the cryptographic security of block ciphers. The pure mathematical nature of the -spectral radius should make the -spectral radius a more appealing measure of security of block ciphers. In a future post, we shall see that the -spectral radius can be used to measure aspects of cryptographic security of block ciphers.