15-th Conference

of the

International Linear Algebra Society

Westin Resort and Spa Cancún, México June 16–20, 2008

Organizing Committee

Rafael Bru Luz María de Alba Daniel Hershkowitz

Andre Klein Beatrice Meini Dale Olesky

Vadim Olshevsky Jeff Stuart Daniel Szyld

Luis Verde-Star

Local Organizing Committee

María José Arroyo, Universidad Autónoma Metropolitana, Iztapalapa

Rubén Martínez-Avendaño, Universidad Autónoma del Estado de Hidalgo

Martha Takane, Instituto de Matemáticas, Universidad Nacional Autónoma de México

Luis Verde-Star (Chair), Universidad Autónoma Metropolitana, Iztapalapa

Acknowledgements

The organizers gratefully acknowledge the support received from:

Consejo Nacional de Ciencia y Tecnología

Rectoría General de la Universidad Autónoma Metropolitana

Rectoría de la UAM-Iztapalapa

División de Ciencias Básicas e Ingeniería, UAM-Iztapalapa

Departamento de Matemáticas, UAM-Iztapalapa

Instituto de Matemáticas, Universidad Nacional Autónoma de México

Dirección General de Asuntos del Personal Académico, UNAM (Proyectos PAPIIT y PAEP)

Universidad Autónoma del Estado de Hidalgo International Linear Algebra Society Taylor and Francis

Abstracts

Ahn, Eunkyung, Kyungpook National University, Daegu, Korea [CT, Thu. 17:45, Room 4]

An extended Lie-Trotter formula and its applications

In this talk we present a class of Lie-Trotter formulae for Hermitian operators including the formulae derived by Hiai-Petz and Furuta. A Lie-Trotter formula for weighted Log-Euclidean geometric means of several positive definite operators is given in terms of Sagae-Tanabe geometric and spectral geometric means. (with Sejong Kim and Yongdo Lim)

Al Zhour, Zeyad, Zarqa Private University, Zarqa, Jordan [CT, Thu. 11:25, Room 5]

Matrix Results on Weighted Drazin Inverse and Some Applications

In this paper, we present two general representations of the weighted Drazin inverse A_{d,W} of an arbitrary rectangular matrix A ∈ M_{m,n} related to Moore-Penrose Inverse (MPI) and Kronecker product of matrices. These generalizations extend earlier results on the Drazin inverse A_{d}, group inverse A_{g} and usual inverse A^{−1}. Furthermore, some necessary and sufficient conditions for Drazin and weighted Drazin inverses are given for the reverse order law (AB)_{d} = B_{d}A_{d} and (AB)_{d,Z} = B_{d,R}A_{d,W} to hold. Finally, we present the solution of the restricted singular matrix equations using our new approaches. (with Adem Kilicman)

Andjelic, Milica, Center for Research on Optimization and Control, Aveiro, Portugal [CT, Fri. 10:35, Room 3]

One upper bound for the largest eigenvalue of the signless Laplacian

We prove several conjectures which were generated using the computer program AutoGraphiX (AGX). New bound on the largest eigenvalue of signless Laplacian is given. Moreover, the study of this bound together with some other already known yields to many examples where the new one gives more precise approximations. (with Slobodan Simic)

Arav, Marina, Georgia State University, Atlanta, GA, USA [CT, Tue. 10:35, Room 3]

Sign Patterns That Require Almost Unique Rank

A sign pattern matrix is a matrix whose entries are from the set {+, −, 0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive (respectively, negative, zero) entry of B by + (respectively, −, 0). For a sign pattern matrix A, the sign pattern class of A, denoted Q(A), is defined as { B : sgn(B) = A }. The minimum rank mr(A) (maximum rank MR(A)) of a sign pattern matrix A is the minimum (maximum) of the ranks of the real matrices in Q(A). Several results concerning sign patterns A that require almost unique rank, that is to say, the sign patterns A such that MR(A) = mr(A) + 1 are established. In particular, a complete characterization of these sign patterns is obtained. Further, the results on sign patterns that require almost unique rank are extended to sign patterns A for which the spread is d = MR(A) − mr(A). (with Frank Hall, Zhongshan Li, Assefa Merid, Yubin Gao)

Aricò, Antonio, Dipartimento di Matematica - Universitá di Cagliari, Cagliari, Italy [MS3, Fri. 11:00, Room 2]

Signal and Image regularization via antireflective transform

The aim of this talk is to show an efficient approach for computing a regularized solution via filtering methods, applied to the spectral decomposition of anti-reflective matrices. Filtering methods are used in signal and image restoration to reconstruct an approximation of a signal or image from degraded measurements. Filtering methods rely on computing a singular value decomposition or a spectral factorization of a large structured matrix. The structure of the matrix depends in part on imposed boundary conditions. Antireflective boundary conditions preserve continuity of the image and its derivative at the boundary, and have been shown to produce superior reconstructions compared to other commonly used boundary conditions, such as periodic, zero and reflective. The purpose of my talk is to analyze the eigenvector structure of matrices that enforce antireflective boundary conditions, and the related anti-reflective transform. An efficient approach to computing filtered solutions is proposed, and numerical tests are shown to illustrate the performance of the discussed methods.

Bardsley, John, University of Montana, Missoula, Montana, USA [MS3, Thu. 17:20, Room 2]

Truncation Rules for Iterative Deblurring Methods

Image data is often collected by a charge coupled device (CCD) camera. CCD camera noise is known to be well-modeled by a Poisson distribution. If this is taken into account, the negative-log of the Poisson likelihood is the resulting data-fidelity function. We derive, via a Taylor series argument, a weighted least squares approximation of the negative-log of the Poisson likelihood function. The image deblurring algorithm of interest is then applied to the problem of minimizing this weighted least squares function subject to a nonnegativity constraint. Our objective in this paper is the development of stopping rules for this algorithm. We present three stopping rules and then test them on data generated using two different true images and an accurate CCD camera noise model. The results indicate that each of the three stopping rules is effective.

Barrett, Wayne, Brigham Young University, Provo, Utah [MS1, Thu. 10:35, Room 1]

Minimum rank of edge subdivisions of complete graphs and wheels

The minimum rank problem for a simple, undirected graph G is to determine the minimum rank (or maximum nullity) over all symmetric matrices whose off-diagonal nonzero pattern corresponds to G. For each positive integer n greater than three, let K_{n} be the complete graph on n vertices and let W_{n} be the wheel on n vertices. Given any graph G, an hG is any graph that can be obtained from G by subdividing edges; G itself is considered to be an hG. We give a general method for finding the minimum rank of any hK_{n} or hW_{n}. For each fixed K_{n} (W_{n}), the problem reduces to identifying among all hK_{n} (hW_{n}) a finite collection of critical graphs; we exhibit these explicitly for small values of n. For each of these we give a sharp upper bound on its minimum rank by constructing a symmetric matrix of minimum rank with the correct zero/nonzero pattern, and a sharp upper bound on the maximum nullity by means of a minimal zero forcing set. The simplest result of this type is as follows. Let K_{4}^{∗} be the graph on 10 vertices obtained by subdividing each edge of K_{4} once, and let G be an hK_{4}. Then

M(G) = \begin{cases}3 if G is not an hK_{4}^{∗} \\ 4 if G is an hK_{4}^{∗}. \end{cases}

where M(G) is the maximum nullity of G. All of our results are field independent. (with Ryan Bowcutt, Mark Cutler, Seth Gibelyou, and Kayla Owens)

Barría, José, Santa Clara University, Santa Clara, U.S.A. [CT, Fri. 16:20, Room 4]

The strong closure of the similarity orbit for a class of pairs of finite rank operators

For operators A and B on a Hilbert space H the similarity orbit S(A, B) is the set of all pairs of the form (W^{−1}AW, W^{−1}BW), where W is an invertible operator on H. We describe the closure of S(A, B) in the strong operator topology, for finite rank operators A and B whose ranges have intersection equal to the subspace {0}.

Baur, Ulrike, Chemnitz University of Technology, Chemnitz, Germany [MS5, Fri. 15:30, Room 2]

Model Reduction for unstable Systems based on Hierarchical Matrix Arithmetic

We consider linear time-invariant (LTI) systems of the following form

Σ : \{ \begin{matrix}ẋ(t) & = & Ax(t) + Bu(t), & t > 0, & x(0) = x^{0}, \\ y(t) & = & Cx(t) + Du(t), & t ≥ 0, \end{matrix}

with A ∈ R^{n×n}, B ∈ R^{n×m}, and C ∈ R^{p×n} arising, e.g., from the discretization and linearization of parabolic PDEs. We will assume that the system Σ is large-scale with n ≫ m, p and that the system is unstable, satisfying

Λ(A) ∩ C^{+} ≠ ∅, Λ(A) ∩ ȷR = ∅.

We further allow the system matrix A to be dense, provided that a data-sparse representation exists. To reduce the dimension of the system Σ, we apply an approach based on the controllability and observability Gramians of Σ. The numerical solution of these Gramians is obtained by solving two algebraic Bernoulli and two Lyapunov equations. As standard methods for the solution of matrix equations are of limited use for large-scale systems, we investigate approaches based on the matrix sign function method. To make this iterative method applicable in the large-scale setting, we incorporate structural information from the underlying PDE model into the approach. By using data-sparse matrix approximations, hierarchical matrix formats, and the corresponding formatted arithmetic we obtain an efficient solver having linear-polylogarithmic complexity. Once the Gramians are computed, a reduced-order system can be obtained applying the usual balanced truncation method.

Beattie, Christopher, Virginia Tech, Blacksburg, VA, USA [MS5, Thu. 11:25, Room 2]

Interpolatory Projection Methods for Parameterized Model Reduction

Dynamical systems are the basic framework for modeling and control of an enormous variety of complex systems. Direct numerical simulation of the associated models has been one of the few means available when goals include accurate prediction or control of complex physical phenomena. However, the ever increasing need for improved accuracy requires the inclusion of ever more detail in the modeling stage, leading inevitably to ever larger-scale, ever more complex dynamical systems Complex systems invariably are parameterized by quantities that will describe particular instances of systems of interest. Simulations in such large-scale settings often must be performed with a variety of different parameter values and these tasks can make unmanageably large demands on computational resources; this is the main motivation for model reduction, which has as its goal production of a much lower dimensional system having the same input/output characteristics as the original system. Rational Krylov subspaces are often capable of providing nearly optimal approximating subspaces for model reduction. A framework for model reduction is presented that includes rational Krylovbased methods as a special case. This broader framework allows retention of special structure in the reduced order models that is often encoded in the system parameterization such as symmetry, second order structure, internal delays, and infinite dimensional subsystems.

Bella, Tom, University of Connecticut, Storrs, USA [MS2, Fri. 11:00, Room 1]

Eigenproblems for quasiseparable matrices

We consider eigenproblems for the class of quasiseparable matrices, or matrices whose off–diagonal blocks are low rank. Classical eigenvalue algorithms, such as QR iterations and divide and conquer, make use of this very property of quasiseparability. We additionally give classifications of Hessenberg–quasiseparable matrices in terms of the recurrence relations of related systems of polynomials. (with Yuli Eidelman, Israel Gohberg and Vadim Olshevsky)

Bengochea, Gabriel, Universidad Autónoma de la Ciudad de México, México D.F. [CT, Fri. 11:00, Room 4]

Duality in the Hopf Algebra of multivariate polynomials

The C-vector space of polynomials in one variable with complex coefficients, which owns a Hopf algebra structure, has a dual space generated by the one variable Taylor’s functionals. In the case of two variables, we can observe that the dual space is generated by the Taylor’s functionals in one variable applied to each variable separately. With this theory we can calculate residues from polynomials of separable variables. This theory can be easily extended to the case of n-variables. There are other theories that develop the residue calculus using Gorenstein algebra. (with L. Verde-Star)

Benner, Peter, TU Chemnitz, Fakultät für Mathematik, Chemnitz, Germany [MS5, Fri. 16:20, Room 2]

Balancing-Related Model Reduction for Large-Scale Unstable Systems

Model reduction is an increasingly important tool in analysis and simulation of dynamical systems, control design, circuit simulation, structural dynamics, CFD, etc. In the past decades many approaches have been developed for reducing the order of a given model. Here, we will focus on balancing-related model reduction techniques that have been developed since the early 80ies in control theory. The mostly used technique of balanced truncation (BT) [3] applies to stable systems only. But there exist several related techniques that can be applied to unstable systems as well. We are interested in techniques that can be extended to large-scale systems with sparse system matrices which arise, e.g., in the context of control problems for instationary partial differential equations (PDEs). Semi-discretization of such problems leads to linear, time-invariant (LTI) systems of the form

\begin{aligned}ẋ(t) & = & Ax(t) + Bu(t), \\ y(t) & = & Cx(t) + Du(t), \end{aligned}  (1)

where A ∈ ℝ^{n×n}, B ∈ ℝ^{n×m}, C ∈ ℝ^{p×n}, D ∈ ℝ^{p×m}, and x^{0} ∈ ℝ^{n}. Here, n is the order of the system and x(t) ∈ ℝ^{n}, y(t) ∈ ℝ^{p}, u(t) ∈ ℝ^{m} are the state, output and input of the system, respectively. We assume A to be large and sparse and n ≫ m, p. Applying the Laplace transform to (1) (assuming x(0) = 0), we obtain

Y (s) = (C(sI − A)^{−1}B + D)U(s) =: G(s)U(s),

where s is the Laplace variable, Y, U are the Laplace transforms of y, u, and G is called the transfer function matrix (TFM) of (1). The TFM describes the input-output mapping of the system. The model reduction problem consists of finding a reduced-order LTI system,

\begin{aligned}˙x̂(t) & = & Âx̂(t) + B̂u(t), \\ ŷ(t) & = & Ĉx̂(t) + D̂u(t), \end{aligned}  (2)

of order r, r ≪ n, with the same number of inputs m, the same number of outputs p, and associated TFM Ĝ(s) = Ĉ(sI − Â)^{−1}B̂ + D̂, so that for the same input function u ∈ L_{2}(0, ∞; ℝ^{m}), we have y(t) ≈ ŷ(t) which can be achieved if G ≈ Ĝ in an appropriate measure. If all eigenvalues of A are contained in the left half complex plane, i.e., [1) is stable, BT is a viable model reduction technique. It is based on balancing the controllability and observability Gramians W_{c}, W_{o} of the system (1) given as the solutions of the Lyapunov equations

AW_{c} + W_{c}A^{T} + BB^{T} = 0,  A^{T} W_{o} + W_{o}A + C^{T} C = 0.  (3)

Based on W_{c}, W_{o} or Cholesky factors thereof, matrices V, W ∈ ℝ^{n×r} can be computed so that with

Â := W^{T} AV, B̂ := W^{T} B, Ĉ := CV, D̂ = D,

the reduced-order TFM satisfies

σ_{r+1} ≤ ∥G − Ĝ∥_{∞} ≤ 2 ∑_{k=r+1}^{n} σ_{k},  (4)

where σ_{1} ≥ … ≥ σ_{n} ≥ 0 are the Hankel singular values of the system, given as the square roots of the eigenvalues of W_{c}W_{o}. The key computational step in BT is the solution of the Lyapunov equations (3). In recent years, a lot of effort has been devoted to the solution of these Lyapunov equations in the large and sparse case considered here. Nowadays, BT can be applied to systems of order up to n = 10^{6}, see, e.g., [1, 2]. Less attention has been payed so far to unstable systems, i.e., systems where A may have eigenvalues with nonnegative real part. Such systems arise, e.g., from semi-discretizing parabolic PDEs with unstable reactive terms. We will review methods related to BT that can be applied in this situation and discuss how these methods can also be implemented in order to become applicable to large-scale problems. The basic idea of these methods is to replace the Gramians W_{c} and W_{o} from (3) by other positive semidefinite matrices that are associated to (1) and to employ the algorithmic advances for BT also in the resulting model reduction algorithms.

References

[1] P. Benner, V. Mehrmann, and D. Sorensen, editors. Dimension Reduction of Large-Scale Systems, volume 45 of Lecture Notes in Computational Science and Engineering. Springer-Verlag, Berlin/Heidelberg, Germany, 2005.

[2] J.-R. Li and J. White. Low rank solution of Lyapunov equations. SIAM J. Matrix Anal. Appl., 24(1):260– 280, 2002.

[3] B. C. Moore. Principal component analysis in linear systems: Controllability, observability, and model reduction. IEEE Trans. Automat. Control, AC-26:17–32, 1981.

Berman, Avi, Technion, Haifa, Israel [MS1, Wed. 12:15, Room 1]

The Colin de Verdière Parameter- a progress report

*** Bini, Dario, Dipartimento di Matematica, Universitá di Pisa, Pisa, Italy [MS6, Tue. 10:35, Room 1]

Fast solution of a certain Riccati Equation through Cauchy-like matrices

We consider a special instance of the algebraic Riccati equation XCX − XE − AX + B = 0 encountered in transport theory, where the n × n matrix coefficients A, B, C, E are rank structured matrices. We present some quadratically convergent iterations for solving this matrix equation based on Newton’s method, Cyclic Reduction and the Structure-preserving Doubling Algorithm. It is shown that the intermediate matrices generated by these iterations are Cauchy-like with respect to a suitable singular operator and their displacement structure is explicitly determined. Using the GKO algorithm enables us to perform each iteration step in O(n^{2}) arithmetic operations. In critical cases where convergence turns to linear, we present an adaptation of the shift technique which allows to get rid of the singularity. Numerical experiments and comparisons which confirm the effectiveness of the new approach are reported. (with Beatrice Meini and Federico Poloni)

Boettcher, Albrecht, TU Chemnitz, Chemnitz, Germany [Plenary, Mon. 15:30–16:25]

Toeplitz matrices with Fisher-Hartwig symbols

Asymptotic properties of large Toeplitz matrices are best understood if the matrix is constituted by the Fourier

coefficients of a smooth function without zeros on the unit circle and with winding number zero. If at least one of these conditions on the generating function is violated, one speaks of Toeplitz matrices with Fisher-Hartwig symbols. The talk is intended as an introduction to the realm of Toeplitz matrices with Fisher-Hartwig symbols for a broad audience. We show that several highly interesting and therefore very popular Toeplitz matrices are just matrices with a Fisher-Hartwig symbol and that many questions on general Toeplitz matrices, for example, the asymptotics of the extremal eigenvalues, are nothing but specific problems for matrices with Fisher-Hartwig symbols. We embark on both classical and recent results concerning the asymptotic behavior of determinants, condition numbers, eigenvalues, and eigenvectors as the matrix dimension goes to infinity.

Boimond, Jean-Louis, LISA - University of Angers, Angers, France [MS7, Tue. 16:55, Room 3]

On Steady State Controller in Min-Plus Algebra

Synchronization phenomena occurring in systems where dynamic behavior is represented by a flow of fluid are well modeled by continuous (min, +)-linear systems. A feedback controller design method is proposed for such systems in order that the system output asymptotically behaves like polynomial input. Such a controller objective is well-known in the conventional linear systems theory. Indeed, the steady-state accuracy of conventional linear systems is classified according to their final responses to polynomial inputs such as steps, ramps, and parabolas. The ability of the system to asymptotically track polynomial inputs is given by the highest degree, k, of the polynomial for which the error between system output and reference input is finite but nonzero. We call the system type k to identify this polynomial degree. For example, a type 1 system has finite, nonzero error to a first-degree polynomial input (ramp). An analogous definition of system type k is given for continuous (min, +)-linear systems and leads to simple conditions as in conventional system theory. In addition to the conditions that the resulting controller must satisfy, we look for the greatest controller to satisfy the just in time criterion. For a manufacturing system, such an objective allows the releasing of raw parts at the latest dates such that the customer demand is satisfied. (with S. Lahaye)

Bourgeois, Gerald, Faculté de Luminy, Marseille, France [CT, Mon. 17:20, Room 4]

About the logarithm function over the matrices

We prove the following results: let x, y be (n, n) complex matrices such that x, y, xy have no eigenvalue in ] − ∞, 0] and log(xy) = log(x) + log(y). If n = 2, or if n ≥ 3 and x, y are simultaneously triangularizable, then x, y commute. In both cases we reduce the problem to a result in complex analysis. Introduction ℤ^{∗} refers to the non-zero integers. Let u be a complex number. Then Re(u), Im(u) refer to the real and imaginary parts of u; if u ∉] − ∞, 0] then arg(u) ∈] − π, π[ refers to its principal argument. Basic facts about the logarithm. Let x be a complex (n, n) matrix which hasn’t any eigenvalue in ]−∞, 0]. Then log(x), the x-principal logarithm, is the (n, n) matrix a such that: e^{a} = x and the eigenvalues of a lie in the strip {z ∈ ℂ : Im(z) ∈] − π, π[}. log(x) always exists and is unique; moreover log(x) may be written as a polynomial in x.

Now we consider two matrices x, y which have no eigenvalue in ] − ∞, 0]:

• If x, y commute then x, y are simultaneously triangularizable and we may associate pairwise their eigenvalues (λ_{j}), (μ_{j}); if moreover ∀j, |arg(λ_{j}) + arg(μ_{j})| < π, then log(xy) = log(x) + log(y).

• Conversely if xy has no eigenvalue in ] − ∞, 0] and log(xy) = log(x) + log(y) then do x, y commute ? We will prove that it’s true for n = 2 (theorem 1) or, for all n, if x, y are simultaneously triangularizable (theorem 2). But if n > 2, then we don’t know the answer in the general case. Dimension 2 Principle of the proof. The proof is based on the two next propositions. The first one is a corollary of a Morinaga and Nono’s result; the second is a technical result using complex analysis. Proposition 1. Let U = {u ∈ ℂ^{∗} : e^{u} = 1 + u}. Let a, b be two (2, 2) complex matrices such that e^{a+b} = e^{a}e^{b} and ab ≠ ba; let spectrum(a) = {λ_{1}, λ_{2}}, spectrum(b) = {μ_{1}, μ_{2}}.

Then one of the three following item is fulfilled:

(1) λ_{1} − λ_{2} ∈ 2iπℤ^{∗} and μ_{1} − μ_{2} ∈ 2iπℤ^{∗}.

(2) One of the following complex numbers ±(λ_{1} − λ_{2}), ±(μ_{1} − μ_{2}) is in U.

(3) a and b are simultaneously similar to (\begin{matrix}λ & 0 \\ 0 & λ + u \end{matrix}) and (\begin{matrix}μ + v & 1 \\ 0 & μ \end{matrix}) with λ, μ ∈ ℂ, u, v ∈ ℂ^{∗}, u ≠ v and

\frac{e^{u} − 1}{u} = \frac{e^{v} − 1}{v} ≠ 0.

Proposition 2. Let u, v be two distinct, non zero complex numbers such that \frac{e^{u} − 1}{u} = \frac{e^{v} − 1}{v} ≠ 0, |Im(u)| < 2π, |Im(v)| < 2π. Then necessarily |Im(u) − Im(v)| ≥ 2π.

Theorem 1. Let x, y be two (2, 2) complex matrices such that x, y, xy haven’t any eigenvalue in ] − ∞, 0] and log(xy) = log(x) + log(y). Then x, y commute. Dimension n I refers to the identity matrix of dimension n − 1. Let ϕ be the holomorphic function: ϕ : z →

\frac{e^{z} − 1}{z}, ϕ(0) = 1.

We’ll use the following to prove our second main result.

Proposition 3. Let a = (\begin{matrix}a_{0} & u \\ 0 & α \end{matrix}) , b = (\begin{matrix}b_{0} & v \\ 0 & β \end{matrix}) be two complex (n, n) matrices where α, β are com-

plex numbers and a_{0}, b_{0} are (n − 1, n − 1) complex matrices which commute; let spectrum(a_{0} − αI) = (α_{i})_{i≤n−1}, spectrum(b_{0} − βI) = (β_{i})_{i≤n−1}. If e^{a+b} = e^{a}e^{b} and ab ≠ ba then one of the following item must be satisfied:

(4) ∃i : β_{i} ≠ 0 and ϕ(α_{i} + β_{i}) = ϕ(α_{i}).

(5) ∃i : α_{i} ≠ 0, β_{i} = 0 and ϕ(−α_{i}) = 1.

Theorem 2. Let x, y be (n, n) complex matrices such that x, y, xy haven’t any eigenvalue in ] − ∞, 0] and log(xy) = log(x) + log(y). If moreover x, y are simultaneously triangularizable then xy = yx.

Conclusion When n = 2, we know how to characterize the complex (n, n) matrices a, b such that ab ≠ ba and e^{a+b} = e^{a}e^{b}; it allowed us to bring back our problem to a result of complex analysis. Unfortunately, if n ≥ 3, the classification of such matrices is unknown. For this reason we can’t prove, in this last case, the hoped result without supplementary assumption.

Brualdi, Richard A., University of Wisconsin - Madison, Madison, USA [MS1, Wed. 10:35, Room 1]

A Conjecture in Combinatorial Matrix Theory

In this talk I will discuss an old conjecture of mine and Bolian Liu, and the recent progress on this conjecture.

Bru, Rafael, Univ. Politécnica, Valencia, Spain [CT, Mon. 18:10, Room 3]

On some classes of H-matrices

This talk deals with some classes of H-matrices which are subclasses of the type of invertible H-matrices, that is H-matrices with invertible comparison matrix. In particular new characterization of S-SDD matrices and α-matrices are given. Properties of those classes of H-matrices and Doubly Diagonally Dominant matrices are considered. (with Ljiljana Cvetković, Vladimir Kostić and Francisco Pedroche)

Bueno Cachadina, María Isabel, The University of California at Santa Barbara, Santa Barbara, USA [CT, Tue. 17:20, Room 4]

Algorithms for computing the Geronimus Transformation

A monic Jacobi matrix is a tridiagonal matrix which contains the parameters of the three-term recurrence relation satisfied by the sequence of monic polynomials orthogonal with respect to a measure. The basic Geronimus transformation with shift α transforms the monic Jacobi matrix associated with a measure dμ into the monic Jacobi matrix associated with dμ/(x − α) + Cδ(x − α), for some constant C. This transformation is known for its numerous applications to quantum mechanics, bispectral transformation in orthogonal polynomials, integrable systems, and other areas of mathematics and mathematical physics. In this talk we examine the algorithms available to compute this transformation and we propose a new algorithm, which is more accurate than the other algorithms when C ≠ 0. We also estimate its forward errors by computing the condition number of the problem. We will finally analyze the particular case when C = 0.

Butkovic, Peter, University of Birmingham, Birmingham, United Kingdom [MS7, Tue. 18:10, Room 3]

On the permuted max-algebraic eigenvector problem

Let a ⊕ b = max(a, b), a ⊗ b = a + b for a, b ∈ \overline{ℝ} := ℝ ∪ \{−∞\} and extend these operations to matrices and vectors as in conventional linear algebra. The following max-algebraic eigenvector problem has been intensively studied in the past: Given A ∈ \overline{ℝ}^{n×n}, find all x ∈ \overline{ℝ}^{n}, x ≠ (−∞, ..., −∞)^{T} ( eigenvectors) such that A ⊗ x = λ ⊗ x for some λ ∈ \overline{ℝ}. In our talk we deal with the permuted eigenvector problem: Given A ∈ \overline{ℝ}^{n×n} and x ∈ \overline{ℝ}^{n}, is it possible to permute the components of x so that the arising vector x′ is a (max-algebraic) eigenvector of A? This problem can be proved to be NP -complete using a polynomial transformation from BANDWIDTH. As a by-product the following permuted max-linear system problem can also be shown NP -complete: Given A ∈ \overline{ℝ}^{m×n} and b ∈ \overline{ℝ}^{m}, is it possible to permute the components of b so that for the arising vector b′ the system A ⊗ x = b′ has a solution? Both problems can be solved in polynomial time when n does not exceed 3.

Carriegos, Miguel, Universidad de León, León, Spain [CT, Tue. 11:50, Room 4]

Reachability of regular switched linear systems

Switched linear systems belong to a special class of hybrid control systems which comprises a collection of subsystems described by linear dynamics (differential/difference equations) together with a switching rule that specifies the switching between the subsystems. Such systems can be used to describe a wide range of physical and engineering problems in practice. On the other hand, switched linear systems have been attracting much attention in the recent past years because of the arising problems are not only academically challenging but also of practical importance. In this talk we consider regular switched sequential linear systems; that is, sequential switched linear systems

Γ : \underline{x}(t + 1) = A_{σ(t)}\underline{x}(t) + B_{σ(t)}\underline{u}(t)

where the switching signals σ(0)σ(1)σ(2)... ∈ Σ^{∗} belong to a regular language L_{Γ} ⊆ Σ^{∗} of admissible sequences of commands of system Γ. This is actually equivalent to saying that switching signals are governed by a finite automaton. We study the notion of reachability in terms of families of matrices A_{σ(−)} and B_{σ(−)} by using linear algebra techniques.

Castro-González, Nieves, Universidad Politécnica de Madrid, Madrid, Spain [CT, Fri. 11:25, Room 4]

Representations for the generalized Drazin inverse of additive perturbations

Let B be a unital complex Banach algebra. An element a ∈ B is said to have a generalized Drazin inverse if there exists x ∈ B such that

xa = ax, x = ax^{2}, a − a^{2}x is quasinilpotent.

In this case, the generalized Drazin inverse of a is unique and is denoted by a^{D}. If in the previous definition a − a^{2}x is in fact nilpotent then a^{D} is the conventional Drazin inverse of a. It is well known that if a and b have generalized Drazin inverse and ab = ba = 0, then (a + b)^{D} = a^{D} + b^{D}. This result was generalized in [Djordjević and Wei, Additive result for the generalized Drazin inverse, J. Austral. Math. Soc. 73 (2002) 115-125] under the one side condition ab = 0. Recently, in [Castro and Koliha, New Additive results for the g-Drazin inverse, Proc. Roy. Soc. Edinburgh Sect. A 134 (2005) 657-666], [Cvetković-Ilić et al., Additive results for the generalized Drazin inverse in a Banach algebra, Linear Algebra Appl. 418 (2006) 53-61], weaker conditions were given under which (a + b)^{D} could be explicitly expressed in terms of a, a^{D}, b, and b^{D}.

In this paper we study the generalized Drazin inverse of the sum a + b, where the perturbation b is a quasinilpotent element, and we obtain a representation for (a + b)^{D} under new conditions which relax the condition ab = 0. Our approach is based on a representation for the resolvent of a 2 × 2 matrix with entries in a Banach algebra, which we provide, and the Laurent expansion of the resolvent in terms of the generalized Drazin inverse. Our results can be applied to obtain different representations of the generalized Drazin inverse

of block matrices M = (\begin{matrix}A & C \\ B & D \end{matrix}), under certain conditions, in terms of the individual blocks. In particular,

we can write M as the sum of a block triangular matrix and a nilpotent matrix and apply the additive perturbation result given to obtain a representation for M^{D}. It extends the result of Meyer and Rose for the Drazin inverse of a block triangular matrix. Finally, we present a numerical example for the Drazin inverse of 2 × 2 block matrices over the complex numbers. This research is partly supported by Project MTM2007-67232, “Ministerio de Educación y Ciencia" of Spain. (with M. F. Martínez-Serrano)

Catral, Minerva, University of Victoria, Victoria, Canada [MS8, Mon. 18:35, Room 1]

The Kemeny Constant in Finite Homogeneous Ergodic Markov Chains

For a finite homogeneous ergodic Markov chain, the Kemeny constant is an interesting quantity which is defined in terms of the mean first passage times and the stationary distribution vector. A formula in terms of group inverses and inverses of associated M-matrices is presented and perturbation results are derived.

Cheng, Wei, National University of Defense Technology, Changsha, P.R. China [CT, Fri. 17:10, Room 4]

One Type of Inverse Eigenvalue Problems in Quaternionic Quantum Mechanics

The inverse eigenvalue problems studied in this paper is investigated in quaternioic quantum mechanics. Sufficient and necessary conditions for the existence of the solutions are given. The constrained least-squares problems are also studied, and the sufficient and necessary conditions for the existence of the solutions are given. At last two numerical algorithm are given. (with Liang-gui Feng)

Corral, Cristina, Universidad Politécnica de Valencia, Valencia, Spain [CT, Mon. 11:10, Room 3]

On Schur complements of H-matrices

In [1] we have partitioned the H-matrices set in three classes: the invertible class, the singular class and the mixed class, depending on the non-singularity of the matrices in the equimodular set. It is well-known that the Schur complements of an H-matrix in the invertible class all are H-matrices (see [2]). In this paper we study the Schur complements of the H-matrices in the mixed and singular classes, obtaining even, under certain conditions, H-matrices in the invertible class.

References

[1] R. Bru, C. Corral, I. Gimenez and J. Mas. On general H-matrices. Lin. Alg. Appl. (2007), doi:10.1016/j.laa.2007.10.030

[2] J. Liu and Y. Huang. Some properties on Schur complements of H-matrices and diagonally dominant matrices. Lin. Alg. Appl., 389 (2004), 365–380.

(with R. Bru, I. Giménez, J. Mas)

Cortés, Vanesa, Universidad de Zaragoza, Zaragoza, Spain [CT, Fri. 15:30, Room 3]

Some properties of the class sign regular matrices and its subclasses

An m × n matrix is called sign regular with signature ε if, for each k ≤ min{m, n}, all its k × k minors have the same sign or are zero. The common sign may differ for different k: the corresponding sequence of signs provides the signature of the sign regular matrix. These matrices play an important role many fields, such as Statistics, Approximation Theory or Computer Aided Geometric Design. In fact, nonsingular sign regular matrices are characterizated as variation-diminishing linear maps: the maximum number of sign changes in the consecutive components of the image of a nonzero vector is bounded above by the minimum number of sign changes in the consecutive components of the vector. We study several properties of these matrices, focusing our analysis on some sublasses of sign regular matrices with certain particular signatures. (with J. M. Peña)

Costa, Liliana, Centre for Research on Optimization and Control, Aveiro, Portugal [CT, Mon. 10:45, Room 4]

Acyclic Birkhoff Polytope

A real square matrix with nonnegative entries and all rows and columns sums equal to one is said to be doubly stochastic. This denomination is associated to probability distributions and it is amazing the diversity of branches of mathematics in which doubly stochastic matrices arise (geometry, combinatorics, optimization theory, graph theory and statistics). Doubly stochastic matrices have been studied quite extensively, especially in their relation with the van der Waerden conjecture for the permanent. In 1946, Birkhoff published a remarkable result asserting that a matrix in the polytope of n × n nonnegative doubly stochastic matrices, Ω_{n} , is a vertex if and only if it is a permutation matrix . In fact, Ω_{n} is the convex hull of all permutation matrices of order n. The Birkhoff polytope Ω_{n} is also known as transportation polytope or doubly stochastic matrices polytope. Recently Dahl discussed the subclass of Ω_{n} consisting of the tridiagonal doubly stochastic matrices and the corresponding subpolytope

Ω_{n}^{t} = {A ∈ Ω_{n} : A is tridiagonal},

the so-called tridiagonal Birkhoff polytope, and studied the facial structure of Ω_{n}^{t}. In this talk we present an interpretation of vertices and edges of the acyclic Birkhoff polytope, 𝔗_{n} = Ω_{n}(T), where T is a given tree, in terms of graph theory. (with C. M. da Fonseca and Enide Andrade Martins)

Cox, Steve, Rice University, Houston, TX, USA [MS2, Thu. 17:20, Room 1]

Eigen-reduction of Large Scale Neuronal Networks

The modest pyramidal neuron has over 100 branches with tens of synapses per branch. Partitioning each branch into 3 compartments, with each compartment carrying say 3 membrane currents, yields at least 20 variables per branch and so, in total, a nonlinear dynamical system of roughly 2000 equations. We linearize this system to, x’=Ax+Bu, y=Cx, where B permits synaptic input into each compartment and C observes only the soma potential. We reduce this system by retaining the dominant singular directions of the associated controllability and observability Grammians. We evaluate the error in soma potential between the full and reduced models for a number of true morphologies over a broad (in space and time) class of synaptic input patterns, and find that reduced systems of dimension less then 10 accurately reflect the full quasi-active dynamics. This savings will permit, for the first time, one to simulate large networks of biophysically accurate cells over realistic time spans. (with Tony Kellems, Derrick Roos and Nan Xiao)

Cravo, Glória, University of Madeira and CELC, Funchal, Portugal [CT, Tue. 10:35, Room 4]

Controllability of Matrices with Prescribed Blocks

Let F be a field and let n, p_{1}, …, p_{k} be positive integers such that n = p_{1} + ⋯ + p_{k}. Let

(C_{1}, C_{2}) = ([ \begin{matrix}C_{1,1} & ⋯ & C_{1,k−1} \\ ⋮ & & ⋮ \\ C_{k−1,1} & ⋯ & C_{k−1,k−1} \end{matrix} ] , [ C_{1,k} ; ⋮ ; C_{k−1,k} ])

where the blocks C_{i,j} are of type p_{i} × p_{j}, i ∈ {1, …, k − 1}, j ∈ {1, …, k}. We study the possibility of (C_{1}, C_{2}) being completely controllable, when some of its blocks are fixed and the others vary.

Our main results analyse the following cases:

(i) All the blocks C_{i,j} are of the same size;

(ii) The blocks C_{i,j} are not necessarily of the same size and k = 3.

We also describe the possible characteristic polynomial of a matrix of the form

C = [ \begin{matrix}C_{1,1} & ⋯ & C_{1,k} \\ ⋮ & & ⋮ \\ C_{k,1} & ⋯ & C_{k,k} \end{matrix} ]

when some of its blocks are prescribed and the others are free.

da Cruz, Henrique F., U.B.I, Covilhã, Portugal [CT, Thu. 18:10, Room 4]

On the matrices that preserve the value of the immanant of the upper triangular matrices

Let χ be an irreducible character of the symmetric group of degree n, let M_{n}(F) be the linear space of n-square matrices with elements in F, let T_{n}^{U}(F) be the subset of M_{n}(F) of the upper triangular matrices and let d_{χ} be the immanant associated with χ. We denote by T (S_{n}, χ) the set of all A ∈ M_{n}(F), such

d_{χ}(AX) = d_{χ}(X),

for all X ∈ T_{n}^{U}(F). In [1] it was proved that if χ is self associated or χ = 1, the principal character, then

T (S_{n}, χ) = ⋃_{σ∈S_{n},χ(σ)≠0}\{P (σ)R : R ∈ T_{n}^{U}(F), det(R) = \frac{χ(id)}{χ(σ)}\}.

If χ is not self associated the problem remains unsolve. In this talk we present a complete description of T (S_{n}, χ) with χ = (n − 1, 1) or χ = (n − 2, 2).

References

[1] R. Fernandes, Matrices that preserve the value of the generalized matrix function of the upper triangular matrices, Linear Algebra Appl. 401 (2005), 47-65. (with Rosário Fernandes)

Damm, Tobias, TU Kaiserslautern, Kaiserslautern, Germany [MS5, Fri. 15:55, Room 2]

Algebraic Gramians and Model Reduction for Different System Classes

Model order reduction by balanced truncation is one of the best-known methods for linear systems. It is motivated by the use of energy functionals, preserves stability and provides strict bounds for the approximation error. The computational bottleneck of this method lies in the solution of a pair of dual Lyapunov equations to obtain the controllability and the observability Gramian, but nowadays there are efficient methods which work for large-scale systems as well. These advantages motivate the attempt to apply balanced truncation also to other classes of systems. For example, there is an immediate way to generalize the idea to stochastic linear systems, where one has to consider generalized versions of Lyapunov equations. Similarly, one can define energy functionals and Gramians for nonlinear systems and try to use them for order reduction. In general, however, these Gramians are very complicated and practically not available. As an approximation, one may use algebraic Gramians, which again are solutions of certain generalized Lyapunov equations and which give bounds for the energy functionals. This approach has been taken e.g. for bilinear systems of the form

ẋ = Ax + ∑_{j=1}^{k} N_{j}xu_{j} + Bu ,
y = Cx ,

which arise e.g. from the discretization of diffusion equations with Robin-type boundary control. In the talk we review these generalizations for different classes of systems and discuss computational aspects.

Day, Jane, San Jose State University, San Jose, CA, USA [CT, Thu. 16:55, Room 3]

Graph Energy Change Due to Edge Deletion

The energy of a graph is the sum of the singular values of its adjacency matrix. We are interested in the effect on energy when one edge is removed, or a set of edges. A singular value inequality for a partitioned matrix proves useful for studying such questions. We describe an infinite family of graphs for which each graph has an edge whose removal leaves the energy unchanged, another family for which removing any edge decreases energy and still another infinite family for which removing any edge increases the energy. We give a sufficient condition on a graph G and edges e such that the energy strictly decreases when e is removed. We have similar results for removing a cut set.

Deaett, Louis, University of Wisconsin-Madison, Madison, WI, USA [MS1, Thu. 12:15, Room 1]

The graph and rank of a positive semidefinite matrix

From a well-known 1991 result of M. Rosenfeld, if A is a positive semidefinite matrix whose corresponding graph G(A) contains no triangle then the number of vertices of G(A) is at most twice the rank of A. This gives

ω(G) ≤ 2 ⇒ mr_{+}(G) ≥ ⌈n/2⌉.

We explore the structure of matrices that achieve this bound, and investigate whether other features of the relationship between mr_{+}(G) and the structure of G can thereby be illuminated.

DeAlba, Luz, Drake University, Des Moines, USA [MS1, Fri. 16:20, Room 1]

The Q-matrix completion problem

A partial matrix is a matrix that contains some specified entries, while all other entries remain unspecified and can be freely assingned a value. An n × n partial matrix, B, specifies a digraph D = (V_{D}, A_{D}), if V_{D} = {1, 2, …, n}, and (i, j) ∈ A_{D} if and only if the entry b_{ij} of B is specified. A real n × n matrix is a Q-matrix if for every k = 1, 2, …, n, the sum of all k × k principal minors is positive. A partial matrix is a partial Q-matrix if the sum of all k × k principal minors is positive for every k for which all k × k principal matrices are fully specified. A digraph D is said to have Q-completion if every partial Q-matrix specifying D can be completed to a Q-matrix. In this presentation we give sufficient conditions for a digraph to have Q-completion, we also give necessary conditions for a digraph to have Q-completion, and characterize those digraphs of order at most four that have Q-completion. (with Leslie Hogben and Bhaba Sharma)

Dhillon, Inderjit, University of Texas, Austin, USA [MS2, Thu. 16:55, Room 1]

On some modified root-finding problems

Modern problems in data analysis require the solution of some interesting matrix nearness problems. One such problem arises when using an information-theoretic distance measure called the von Neumann matrix divergence (related to von Neumann entropy). The matrix nearness problem in turn leads to a modified rootfinding problem involving the matrix exponential. In this talk, I will show how the Newton method can be applied to solve this problem. The central issue is the efficient calculation of the derivative which involves the matrix exponential and a “diagonal + low-rank” eigenvalue problem. (with Matyas Sustik)

Dodig, Marija, CELC, Universidade de Lisboa, Lisbon, Portugal [CT, Mon. 10:45, Room 3]

Singular systems, state feedback problem

In this talk, the strict equivalence invariants by state feedback for singular systems are studied. As the main result we give the necessary and sufficient conditions under which there exists a state feedback such that the resulting system has prescribed pole structure as well as row and column minimal indices. This result presents a generalization of previous results of state feedback action on singular systems.

Dogan-Dunlap, Hamide, UTEP, El Paso, TX, USA [MS4, Mon. 11:10, Room 1]

Thinking Modes Revealed on Students’ Responses from an Assignment on Linear Independence

The main goal of our work was to document differences on the type of modes students use after being exposed to two different interventions. Both interventions used computer-based activities providing numerical (first intervention) and geometrical (second intervention) representations. Only the modes displayed on student responses from an assignment that was given during the second intervention are reported here. This assignment consisted of seven questions on linear independence. The aspects of forty-five matrix algebra students’ thinking modes are documented in light of Sierpinska’s framework on thinking modes (2000)*. Our qualitative analysis implemented a constant comparison method, an inductive approach to classifying responses through emerging themes. Our analysis revealed that, in concrete (traditional) questions that do not require generalization/abstraction, students’ responses included various geometrical aspects of vectors and planes in R^{3}. Some of which are as follows: “vectors coming out of a plane," “Vectors that lie on the same plane," and “the magnitude of vectors are the same/different." Even though, students used graphical modes in their responses for the concrete questions, when answering more abstract questions requiring conjecture and generalization, many of these students’ responses fell back on the algebraic and arithmetic modes. Some for instance stated mainly the formal definition of linear independence without showing any work/computation to justify their answers for these questions. We should also note that despite this fact, the second most common mode used in the abstract questions were geometrical. We furthermore observed that the notable number of students made arguments using multiple modes; numerical, algebraic and geometrical. One may infer from this that, at this point, students may begin reasoning in multiple modes. We believe that this is a desired behavior toward forming a rich conceptual understanding of linear independence. *Sierpinska, A. 2000. On some aspects of students’ thinking in linear algebra, The Teaching of Linear Algebra in Question, The Netherlands 2000, pp. 209–246.

Dolinar, Gregor, Faculty of Electrical Engineering, Ljubljana, Slovenia [CT, Thu. 17:20, Room 4]

General preservers of quasi-commutativity

Let M_{n} be the algebra of all n × n matrices over the complex field ℂ. We say that A, B ∈ M_{n} quasi-commute if there exists a nonzero ξ ∈ ℂ such that AB = ξBA. In the paper we classify bijective not necessarily linear maps Φ: M_{n} → M_{n} which preserve quasi-commutativity in both directions. (with Bojan Kuzma)

Domínguez, María Elena, Universidad Politécnica de Madrid, Madrid, Spain [CT, Mon. 17:20, Room 3]

General solution of certain matrix equations arising in filter design applications

In this work we present the explicit expression of all rectangular Toeplitz matrices B, C which verify the equation BB^{H} + CC^{H} = aI for some a > 0. This matrix equation arises in some signal processing problems. For instance, it appears when designing the even and odd components of paraunitary filters, which are widely used for signal compression and denoising purposes. We also point out the relationship between the above matrix equation and the polynomial Bezout equation |B(z)|^{2} + |C(z)|^{2} = a > 0 for |z| = 1. By exploiting this fact, our results also yield a constructive method for the parameterization of all solutions B(z), C(z). The main advantage of our approach is that B are C are built without need of spectral factorization. Besides these theoretical advances, in order to illustrate the effectiveness of our approach, some examples of paraunitary filters design are finally given.

Dopazo, Esther, Facultad de Informática. Universidad Politécnica de Madrid, Boadilla del Monte, Madrid, Spain [CT, Fri. 10:35, Room 4]

Further results on the representation of the Drazin inverse of a 2 × 2 block matrix

Let A be an n × n complex matrix. The Drazin inverse of A is the unique matrix A^{D} satisfying the relations:

A^{D}AA^{D} = A^{D}, A^{D}A = AA^{D}, A^{k+1}A^{D} = A

where k = Ind(A), the index of A, is the smallest nonnegative integer such that rank(A^{k}) = rank(A^{k+1}). The concept of Drazin inverse plays an important role in various fields like Markov chains, singular differential and difference equations, iterative methods, etc. A challenge of great interest in

this area is to establish an explicit representation for the Drazin inverse of a 2×2 block matrix M = (\begin{matrix}A & B \\ C & D \end{matrix}),

where A and D are square matrices, in terms of A^{D} and D^{D} with arbitrary blocks A, B, C and D. It was posed as an open problem by Campbell and Meyer in 1979, in conecction with the problem to find general expressions for the solutions of the second-order system of the differential equations

Ex′′(t) + F x′(t) + Gx(t) = 0,

where the matrix E is singular. Starting from the general formula given by C. D. Meyer and N. J. Rose [6] for the Drazin inverse of triangular block matrices (B = 0 or C = 0), an intensive research has been developed on this topic. Recently, some partial results have been obtained under specific conditions [1-5,7]. In this paper, we provide an explicit formula for 2 × 2 block matrices assuming the geometrical condition

R(B) ⊂ N (C) ∩ N (D)

where R(·) and N (·) denote the range and the null space of the corresponding matrix, respectively. It generalizes results given by R. E. Hartwig, X. Li and Y. Wei [4] and by D. S. Djordjevic and P. S. Stanmirovic [3]. From our main result, some special cases and perturbation results are derived. This research has been partly supported by project MTM2007-67232, “Ministerio de Educación y Ciencia" of Spain.

References

[1] D. Cvetkovic-Ilic, A note on the representation for the Drazin inverse of 2 × 2 block matrices, Linear Algebra and its applications (2008), doi:10.1016/j.laa.2008.02.019.

[2] N. Castro-González, E. Dopazo, J. Robles, Formulas for the Drazin inverse of special block matrices, Appl. Math. Comput., 174 (2006), 252–270.

[3] D. S. Djordjević, P. S. Stanimirović, On the generalized Drazin inverse and generalized resolvent, Czechoslovak Math. J., 51 (126) (2001), 617–634.

[4] R. E. Hartwig, X. Li, Y. Wei, Representations for the Drazin inverse of a 2 × 2 block matrix, SIAM J. Matrix Anal. Appl., 27 (2006) 757–771.

[5] X. Li, Y. Wei, A note on the representations for the Drazin inverse of 2×2 block matrices, Linear Algebra Appl. 423 (2007) 332–338.

[6] C.D. Meyer, Jr., N. J. Rose, The index and the Drazin inverse of block triangular matrices, SIAM J. Appl. Math. 33 (1977), 1–7.

[7] Y. Wei, Expression for the Drazin of 2×2 block matrix, Linear and Multilinear Algebra 45 (1998) 131–146.

(with M. F. Martínez-Serrano and N. Castro-González)

Esen, Özlem, Anadolu University, Eskisehir, Turkey [CT, Fri. 17:10, Room 3]

On The Root Clustering of Matrices

Root clustering problems of matrices are considered. Here we are given conditions for eigenvalues of a matrix to lie in a prescribed subregion 𝔻 of the complex plane. The region 𝔻 (stability region ) is defined by rational functions. A simple necessary and sufficient condition for stability of a single matrix is obtained. For a commutting polynomial family a necessary and sufficient condition in terms of a common solution to a set of Lyapunov inequalities is derived. A simple sufficient condition for the Hurwitz stability of a commutting quadratic polynomial matrix family is given.

Estatico, Claudio, Universitá di Cagliari, Cagliari, Italy [MS3, Fri. 10:35, Room2]

Block splitting least square regularization for structured matrices arising in nonlinear microwave imaging

Nonlinear inverse problems arising in a lot of real applications generally leads to very large scaled and structured matrices, which require a wide analysis in order to reduce the numerical complexity, both in time and space. Since these problems are ill-posed, any solving strategy based on linearization involves a some least square regularization. In this talk a microwave imaging problem is introduced: the dielectric properties of an object under test (i.e., the output image to restore) are retrieved by means of its scattered microwave electromagnetic field (i.e., the input data). By a theoretical point of view, the mathematical model is a nonlinear integral equation with structured shift variant integral kernel. By a numerical point of view, the linearization and discretization gives rise to an ill-conditioned block arrow matrix with structured blocks, which is iteratively solved by a three-level regularizing Inexact-Newton scheme as follows: (i) the first (outer) level of iterations is related to a least square Gauss-Newton linearization; the second level of iterations is related to a block splitting iterative scheme; (iii) the third and nested inner level of iterations is related to a regularization iterative method for any system block arising from any level II iteration. After that, post-processing techniques based on linear super-resolution improves the quality of the results, and some numerical results are given and compared. This is a joint work with Professor J. Nagy of the Emory University, Atlanta, and Professors F. Di Benedetto, M. Pastorino, A. Randazzo and G. Bozza, of the University of Genova, Italy.

Bibliography

C. Estatico, G. Bozza, A. Massa, M. Pastorino, A. Randazzo, “A two steps inexact-Newton method for electromagnetic imaging of dielectric structures from real data”, Inverse Problems, 21, pp. S81–S94, 2005. C. Estatico, G. Bozza, M. Pastorino, A. Randazzo, “An Inexact-Newton method for microwave reconstruction of strong scatterers”, IEEE Antennas and Wireless Propagation Letters, 5, pp. 61-64, 2006. F. Di Benedetto, C. Estatico, J. Nagy, “Numerical linear algebra for nonlinear microwave imaging”, in preparation. *with J. Nagy, F. di Benedetto, M. Pastorino, A. Randazzo, and G. Boza)

Eubanks, Sherod, Washington State University, Pullman, USA [MS8, Mon. 18:10, Room 1]

Generalized Soules Matrices

I will discuss a generalization of Soules matrices and its application to the nonnegative inverse eigenvalue problem, eventually nonnegative matrices, and exponentially nonnegative matrices.

Fassbender, Heike, TU Braunschweig, Braunschweig, Germany [Plenary, Thu. 8:10–9:05]

Structured Methods for Eigenproblems with Hamiltonian Spectral Symmetry

Introduction

It usually takes a long process of simplifications, linearizations and discretizations before one comes up with the problem of computing the eigenvalues or invariant subspaces of a matrix. These techniques typically lead to highly structured matrix representations, which, for example, may contain redundancy or inherit some physical properties from the original problem. As a simple example, let us consider a quadratic eigenvalue problem of the form

(λ^{2}I_{n} + λC + K)x = 0,  (5)

where C ∈ ℝ^{n×n} is skew-symmetric (C = −C^{T}), K ∈ ℝ^{n×n} is symmetric (K = K^{T}), and I_{n} denotes the n × n identity matrix. Eigenvalue problems of this type arise, e.g., from gyroscopic systems [8, 12] or Maxwell equations [9]; they have the physically relevant property that all eigenvalues appear in quadruples {λ, −λ, λ̄, −λ̄}, i.e., the spectrum is symmetric with respect to the real and imaginary axes.

Linearization turns (5) into a matrix eigenvalue problem, e.g., the eigenvalues of (5) can be obtained from the eigenvalues of the matrix

A = [ \begin{matrix}−\frac{1}{2}C & \frac{1}{4}C^{2} − K \\ I_{n} & −\frac{1}{2}C \end{matrix} ] .  (6)

This 2n × 2n matrix is structured, its 4n^{2} entries depend only on the n^{2} entries necessary to define C and K. The matrix A has the particular property that it is a Hamiltonian matrix, i.e., A is a two-by-two block matrix of the form

[ \begin{matrix}B & G \\ Q & −B^{T} \end{matrix} ] , G = G^{T} , Q = Q^{T} , B, G, Q ∈ ℝ^{n×n}.

Considering A to be Hamiltonian does not capture all the structure present in A but it captures an essential part: the spectrum of any Hamiltonian matrix is symmetric with respect to the real and and imaginary axes.

Hamiltonian matrices also arise in applications related to linear control theory for continuous-time systems [1]. Deciding whether a certain Hamiltonian matrix has purely imaginary eigenvalues is the most critical step in algorithms for computing the stability radius of a matrix or the H_{∞} norm of a linear time-invariant system, see, e.g., [5, 6].

When computing the eigenvalues of a Hamiltonian eigenvalue problem with a standard method like the QR method, the computed eigenvalues will not obey the eigenvalue pairing {λ, −λ, λ̄, −λ̄}, for complex eigenvalues with nonzero real part and {λ, −λ} for real and purely imaginary eigenvalues. The described eigenvalue pairings often reflect important properties of the underlying application and should thus be preserved in finite-precision arithmetic. Numerical methods that take this structure into account are capable of preserving the eigenvalue pairings of the original eigenvalue problem (5), despite the presence of roundoff and other approximation errors. Besides the preservation of such eigenvalue symmetries, there are several other benefits to be gained from using structure-preserving algorithms in place of general-purpose algorithms for computing eigenvalues. These benefits include reduced computational time and improved eigenvalue/eigenvector accuracy.

QR-like algorithms that achieve this goal have been developed in [4, 6, 13] while Krylov subspace methods tailored to Hamiltonian matrices can be found in [2, 3, 7, 8, 14]. In this talk, we will review these methods concentrating on the symplectic Lanczos method endowed with an implicit restarting strategy. Unfortunately, the implementation of efficient locking and purging strategies for this method turns out to be even more complicated than in the non-structured, implicitly restarted Arnoldi (IRA) method. An elegant away around this difficulty was presented for IRA by Stewart [10, 11], using a Krylov-Schur decomposition technique. In this talk, we will discuss the application of this idea for the symplectic Lanczos process. This will lead to fairly easy implementable purging and locking strategies which improve the convergence properties of the structured eigensolver based on the symplectic Lanczos process significantly. We demonstrate the efficiency of the new scheme by testing the algorithm on several linear and quadratic eigenproblems with Hamiltonian spectral symmetry.

This is joint work with Peter Benner (TU Chemnitz, Germany) and Martin Stoll (University of Oxford, England).

References

[1] P. Benner. Computational methods for linear-quadratic optimization. Supplemento ai Rendiconti del Circolo Matematico di Palermo, Serie II, No. 58:21–56, 1999.

[2] P. Benner and H. Faßbender. An implicitly restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem. Linear Algebra Appl., 263:75–111, 1997.

[3] P. Benner, D. Kressner, and V. Mehrmann. Skew-Hamiltonian and Hamiltonian eigenvalue problems: Theory, algorithms and applications. In Z. Drmač, M. Marušić, and Z. Tutek, editors, Proceedings of the Conference on Applied Mathematics and Scientific Computing, Brijuni (Croatia), June 23-27, 2003, pages 3–39. Springer-Verlag, 2005.

[4] P. Benner, V. Mehrmann, and H. Xu. A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils. Numer. Math., 78(3):329–358, 1998.

[5] S. Boyd, V. Balakrishnan, and P. Kabamba. A bisection method for computing the H_{∞} norm of a transfer matrix and related problems. Math. Control, Signals, Sys., 2:207–219, 1989.

[6] R. Byers. A Hamiltonian QR algorithm. SIAM J. Sci. Statist. Comput., 7(1):212–229, 1986.

[7] W. R. Ferng, W.-W. Lin, and C.-S. Wang. The shift-inverted J-Lanczos algorithm for the numerical solutions of large sparse algebraic Riccati equations. Comput. Math. Appl., 33(10):23–40, 1997.

[8] V. Mehrmann and D. S. Watkins. Structure-preserving methods for computing eigenpairs of large sparse skew-Hamiltonian/Hamiltonian pencils. SIAM J. Sci. Comput., 22(6):1905–1925, 2000.

[9] F. Schmidt, T. Friese, L. Zschiedrich, and P. Deuflhard. Adaptive multigrid methods for the vectorial Maxwell eigenvalue problem for optical waveguide design. In W. Jäger and H.-J. Krebs, editors, Mathematics. Key Technology for the Future, pages 279–292, 2003.

[10] G.W. Stewart, A Krylov-Schur algorithm for large eigenproblems, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 601–614.

[11] , Matrix Algorithms, Volume II: Eigensystems, SIAM, Philadelphia, USA, 2001.

[12] F. Tisseur and K. Meerbergen. The quadratic eigenvalue problem. SIAM Rev., 43(2):235–286, 2001.

[13] C. F. Van Loan. A symplectic method for approximating all the eigenvalues of a Hamiltonian matrix. Linear Algebra Appl., 61:233–251, 1984.

[14] D. S. Watkins. On Hamiltonian and symplectic Lanczos processes. Linear Algebra Appl., 385:23–45, 2004.

(with Peter Benner (TU Chemnitz, Germany) and Martin Stoll (University of Oxford, England))

Fassbender, Heike, TU Braunschweig, Braunschweig, Germany [MS6, Tue. 11:00, Room1]

On the numerical solution of large-scale sparse discrete-time Riccati equations

Inspired by a large-scale sparse discrete-time Riccati equation which arises in a spectral factorization problem the efficient numerical solution of such Riccati equations is studied in this work. Spectral factorization is a crucial step in the solution of linear quadratic estimation and control problems. A variety of methods has been developed over the years for the computation of canonical spectral factors for processes with rational spectral densities, see, e.g., the survey [6]. One approach involves the spectral factorization via a discrete-time Riccati equation. Whenever possible, we consider the generalized discrete–time algebraic Riccati equation

0 = R(X) = C^{T} QC + A^{T} XA − E^{T} XE  (7)
−(A^{T} XB + C^{T} S)(R + B^{T} XB)^{−1}(B^{T} XA + S^{T} C),

where A, E ∈ ℝ^{n×n}, B ∈ ℝ^{n×m}, C ∈ ℝ^{p×n}, Q ∈ ℝ^{p×p}, R ∈ ℝ^{m×m}, and S ∈ ℝ^{p×m}. Furthermore, Q and R are assumed to be symmetric and A and E are large and spare. For the particular application above, we have

A = [ \begin{matrix}0 & 1 \\ & ... & ... \\ & & 0 & 1 \\ & & & 0 \end{matrix} ] .

The function R(X) is a rational matrix function, R(X) = 0 defines a system of nonlinear equations. Newton’s method for the numerical solution of DAREs can be formulated as follows

for k = 0, 1, 2, …

1. K_{k} ← K(X_{k}) = (R + B^{T} X_{k}B)^{−1}(B^{T} X_{k}A + S^{T} C).

2. A_{k} ← A − BK_{k}.

3. R_{k} ← R(X_{k}).

4. Solve for N_{k} in the Stein equation

A_{k}^{T} N_{k}A_{k} − E^{T} N_{k}E = −R_{k}.  (8)

5. X_{k+1} ← X_{k} + N_{k}. end for

The computational cost for this algorithm mainly depends upon the cost for the numerical solution of the Stein equation (8). This can be done using the Bartels–Stewart algorithm [1] or an extension to the case E ≠ I [2, 3, 4]. The Bartels-Stewart algorithm is the standard direct method for the solution of Stein equations of small to moderate size. This method requires the computation of a Schur decomposition, and thus is not appropriate for large scale problems. The cost for the solution of the Stein equation is ≈ 73n^{3} flops. Iterative schemes have been developed including the Smith method [7], the sign-function method [5], and the alternating direction implicit (ADI) iteration method [8]. Unfortunately, all of these methods compute the solution in dense form and hence require O(n^{2}) storage. In case the solution to the Stein equation has low numerical rank (i.e., the eigenvalues decay rapidly) one can take advantage of this low rank structure to obtain approximate solutions in low rank factored form. If the effective rank is r ≪ n, then the storage is reduced from O(n^{2}) to O(nr). This approach will be discussed here in detail.

References

[1] R.H. Bartels and G.W. Stewart, Solution of the matrix equation AX + XB = C: Algorithm 432, Comm. ACM, 15 (1972), pp. 820–826.

[2] J.D. Gardiner, A.J. Laub, J.J. Amato, and C.B. Moler, Solution of the Sylvester matrix equation AXB + CXD = E, ACM Trans. Math. Software, 18 (1992), pp. 223–231.

[3] J.D. Gardiner, M.R. Wette, A.J. Laub, J.J. Amato, and C.B. Moler, Algorithm 705: A Fortran-77 software package for solving the Sylvester matrix equation AXB^{T} + CXD^{T} = E, ACM Trans. Math. Software, 18 (1992), pp. 232–238.

[4] T. Penzl, Numerical solution of generalized Lyapunov equations, Adv. Comp. Math., 8 (1997), pp. 33–48.

[5] J.D. Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Internat. J. Control, 32 (1980), pp. 677–687. (Reprint of Technical Report No. TR-13, CUED/B-Control, Cambridge University, Engineering Department, 1971).

[6] A.H. Sayed and T. Kailath, A survey of spectral factorization methods, Num. Lin. Alg. Appl., 8 (2001), pp. 467–496.

[7] R.A. Smith, Matrix equation XA + BX = C, SIAM J. Appl. Math., 16 (1968), pp. 198–201.

[8] E.L. Wachspress, Iterative solution of the Lyapunov matrix equation, Appl. Math. Letters, 107 (1988), pp. 87–90.

(with Peter Benner)

Feng, Lihong, Faculty of Mathematics, TU Chemnitz, Chemnitz, Germany [MS5, Thu. 11:50, Room 2]

Parametric Model Reduction for Systems with Coupled Parameters

We consider model order reduction of parametric systems with parameters which are nonlinear functions of the frequency parameter s. Such systems result from, for example, the discretization of electromagnetic systems with surface losses [1]. Since the parameters are functions of the frequency s, they are highly coupled with each other. We see them as individual parameters when we implement model order reduction. By analyzing existing methods of computing the projection matrix for model order reduction, we show the applicability of each method and propose an optimized method for the parametric system considered in this paper. The transfer function of the parametric systems considered here take the form

H(s) = sB^{T}(s^{2}I_{n} − 1/\sqrt{s}D + A)^{−1}B,  (9)

where A, D and B are n × n and n × m matrices, respectively, and I_{n} is the identity of suitable size. To apply parametric model order reduction to (9), we first expand H(s) into a power series. Using a series expansion about an expansion point s_{0}, and defining σ_{1} := \frac{1}{s^{2}\sqrt{s}} − \frac{1}{s_{0}^{2}\sqrt{s_{0}}} , σ_{2} := \frac{1}{s^{2}} − \frac{1}{s_{0}^{2}} , we may use the three different methods below to compute a projection matrix V and get the reduced-order transfer function

Ĥ(s) = sB̂^{T}(s^{2}I_{r} − 1/\sqrt{s}D̂ + Â)^{−1}B̂,

where Â = V^{T} AV, B̂ = V^{T} B, etc., and V is an n × r projection matrix with V^{T} V = I_{r}. To simplify notation, in the following we use G := I − \frac{1}{s_{0}^{2}\sqrt{s_{0}}} D + \frac{1}{s_{0}^{2}} A, B_{M} := G^{−1}B, M_{1} := G^{−1}D, and M_{2} := −G^{−1}A.

Directly computing V

A simple and direct way for obtaining V is to compute the coefficient matrices in the series expansion

\begin{aligned}H(s) & = & \frac{1}{s}B^{T}[B_{M} + (M_{1}B_{M}σ_{1} + M_{2}B_{M}σ_{2}) + (M_{1}^{2}B_{M}σ_{1}^{2} \\ & & +(M_{1}M_{2} + M_{2}M_{1})B_{M}σ_{1}σ_{2} + M_{2}^{2}B_{M}σ_{2}^{2}) + (M_{1}^{3}B_{M}σ_{1}^{3} + …) + …], \end{aligned}  (10)

by direct matrix multiplication and orthogonalize these coefficients to get the matrix V [2]. After the coefficients B_{M}, M_{1}B_{M}, M_{2}B_{M}, M_{1}^{2}B_{M}, (M_{1}M_{2} + M_{2}M_{1})B_{M}, M_{2}^{2}B_{M}, M_{1}^{3}B_{M}, … are computed, the projection matrix V can be obtained by

range{V } = orthogonalize{B_{M}, M_{1}B_{M}, M_{2}B_{M}, M_{1}^{2}B_{M}, (M_{1}M_{2} + M_{2}M_{1})B_{M}, M_{2}^{2}B_{M}, M_{1}^{3}B_{M}, …} (11)

Unfortunately, the coefficients quickly become linearly dependent due to numerical instability. In the end, the matrix V is often so inaccurate that it does not possess the expected theoretical properties.

Recursively computing V

The series expansion (10) can also be written into the following formulation:

H(s) = \frac{1}{s}[B_{M} + (σ_{1}M_{1} + σ_{2}M_{2})B_{M} + … + (σ_{1}M_{1} + σ_{2}M_{2})^{i}B_{M} + …]  (12)

Using (12), we define

R_{0} = B_{M}, ; R_{1} = [M_{1}, M_{2}]R_{0}, ; ⋮ ; R_{j} = [M_{1}, M_{2}]R_{j−1}, ; ⋮.  (13)

We see that R_{0}, R_{1}, …, R_{j}, … include all the coefficient matrices in the series expansion (12). Therefore, we can use R_{0}, R_{1}, …, R_{j}, … to generate the projection matrix V:

range{V } = colspan{R_{0}, R_{1}, …, R_{m}}.  (14)

Here, V can be computed employing the recursive relations between R_{j}, j = 0, 1, …, m combined with the modified Gram-Schmidt process [3].

Improved algorithm for recursively computing V

Note that the coefficients M_{1}M_{2}B_{M} and M_{2}M_{1}B_{M} are two individual terms in (13), which are computed and orthogonalized sequentially within the modified Gram-Schmidt process. Observing that they are actually both coefficients of σ_{1}σ_{2}, they can be combined together as one term during the computation as in (11). Based on this, we develop an algorithm which can compute V in (11) by a modified Gram-Schmidt process. By this algorithm, the matrix V is numerically stable which guarantees the accuracy of the reduced-order model. Furthermore, the size of the reduced-order model is smaller than that of the reduced-order model derived by (14). Therefore, this improved algorithm is optimal for the parametric system considered in this paper.

[1] T. Wittig, R. Schuhmann, and T. Weiland. Model order reduction for large systems in computational electromagnetics. Linear Algebra and its Applications, 415(2-3):499-530, 2006.

[2] L. Daniel, O.C. Siong, L.S. Chay, K.H. Lee, and J. White. A multiparameter moment-matching modelreduction approach for generating geometrically parameterized interconnect performance models. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 22 (5):678–693, 2004.

[3] L. Feng and P. Benner. A Robust Algorithm for Parametric Model Order Reduction. Proc. Appl. Math. Mech., 7, 2008 (to appear).

This research is supported by the Alexander von Humboldt-Foundation and by the research network SyreNe — System Reduction for Nanoscale IC Design within the program Mathematics for Innovations in Industry and Services (Mathematik für Innovationen in Industrie und Dienstleistungen) funded by the German Federal Ministry of Education and Science (BMBF). (with Peter Benner)

Fernandes, Rosário, Centro de Estruturas Lineares e Combinatórias (CELC), Lisboa, Portugal [CT, Mon. 11:10, Room 4]

Rank partitions and covering numbers under small perturbations of an element

Let (v_{1}, …, v_{m}) be a family of vectors of C^{n} (where C is the field of complex numbers). Let k be a positive integer. A subfamily (v_{i_{1}}, …, v_{i_{j}}) of (v_{1}, …, v_{m}) is k-independent if it is the union of k subfamilies each of which is linearly independent. The k-dimension of (v_{1}, …, v_{m}) (denoted by d_{k}(v_{1}, …, v_{m})) is the maximum cardinality of the k-independent subfamilies of (v_{1}, …, v_{m}). It was proved in “On the μ-colorings of a matroid" (J.A. Dias da Silva, Lin. Multil. Algebra 27 (1990), 25-32) that

(d_{1}(v_{1}, …, v_{m}), d_{2}(v_{1}, …, v_{m}) − d_{1}(v_{1}, …, v_{m}), …, d_{m}(v_{1}, …, v_{m}) − d_{m−1}(v_{1}, …, v_{m}))

is a partition of the number of the nonzero vectors in the family (v_{1}, …, v_{m}). This partition is called the rank partition. Let v_{i} ∈ (v_{1}, …, v_{m}) be a nonzero vector. The smallest integer s such that d_{s}(v_{1}, …, v_{m}) > d_{s}(v_{1}, …, v_{i−1}, v_{i+1}, …, v_{m}) is called the covering number of v_{i} in (v_{1}, …, v_{m}). In this talk we describe how the rank partition and the covering number can change with arbitrarily small perturbations of a fixed element.

Ferrer, Josep, Universitat Politecnica de Catalunya, Barcelona, Spain [CT, Tue. 12:15, Room 4]

Geometric structure of the equivalence classes of a controllable pair

It is well known, in quite general conditions, the geometric structure of the orbits generated by the action of a group in a differentiable manifold. It seems natural to ask for the geometric relationships when different subgroups are considered, that is to say, the geometric structure of the different suborbits forming a lattice, and specially their intersections (which in general must not be an orbit, even not a differentiable manifold). Here, we present a full unified panorama in the case of pairs of matrices representing linear systems, where different equivalent relations can be considered: changes of basis in the state space and in the input space, and feedbacks. The starting tools in this analysis are the Arnold’s techniques of versal deformations. More specifically, we use two versal deformations of a pair of matrices with regard to the block similarity, and when only changes in the state space are allowed. Some interesting comments and remarks are derived concerning the role of different kind of feedbacks, the boundary of the suborbits, the effects of perturbing a pair... (with A. Compta and M. Peña)

Fonseca, Carlos, Department of Mathematics, University of Coimbra, Coimbra, Portugal [CT, Thu. 12:15, Room 3]

An inequality for the multiplicity of an eigenvalue

Let A(G) be a Hermitian matrix whose graph G is given. From the interlacing theorem, it is known that m_{A(G\i)}(θ) ≥ m_{A(G)}(θ) − 1, where m_{A(G)}(θ) is the multiplicity of the eigenvalue θ of A(G). Motivated by the Christoffel-Darboux Identity, in this talk we provide a similar inequality when a particular path of G is deleted.

Fošner, Ajda, Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia [CT, Mon. 11:35, Room 3]

Commutativity preserving maps on real matrices

Let M_{n}(ℝ) be the algebra of all n × n real matrices. A map ϕ : M_{n}(ℝ) → M_{n}(ℝ) preserves commutativity if ϕ(A)ϕ(B) = ϕ(B)ϕ(A) whenever AB = BA, A, B ∈ M_{n}(ℝ). If ϕ is bijective and both ϕ and ϕ^{−1} preserve commutativity, then we say that ϕ preserves commutativity in both directions. We will talk about non-linear maps on M_{n}(ℝ) that preserve commutativity in both directions or in one direction only.

Frank, Martin, University of Kaiserslautern, Kaiserslautern, Germany [CT, Tue. 17:45, Room 4]

An iterative method for transport equations in radiotherapy

Treatment with high energy ionizing radiation is one of the main methods in modern cancer therapy that is in clinical use. During the last decades two main approaches to dose calculation were used, Monte Carlo simulations and pencil-beam models. A third way to dose calculation has not attracted much attention in the medical physics community. This approach is based on deterministic transport equations of radiative transfer. In this work, we study a full discretization of the transport equation which yields a large linear system of equations. The computational challenge is that scattering is strongly forward-peaked, which means that traditional solution methods like source iteration fail in this case. Therefore we propose a new method, which combines an incomplete factorization of the scattering matrix and several iterative steps to obtain a fast and accurate solution. Numerical examples are given. (with Bruno Dubroca)

Freund, Roland, University of California, Davis, CA, USA [MS5, Thu. 12:15, Room 2]

The Effects of Deflation in Projection-Based Order Reduction

In recent years, there has been a lot of interest in order reduction of large-scale linear dynamical systems. Many of the widely-used methods today employ some form of projection onto suitably chosen block Krylov subspaces. It is well understood that numerically robust techniques for constructing bases for these block Krylov subspaces need to be able to handle deflation of linearly dependent or nearly linearly dependent Krylov vectors; the case of linearly dependent vectors is called exact deflation, the case of nearly linearly dependent vectors is called inexact deflation. It is also well known that, at least in exact arithmetic, the occurrence of exact deflation is a desirable event, in the sense that it increases the accuracy of the reduced-order model. On the other hand, in order to have numerical stable procedures, in finite-precision arithmetic, one needs to perform inexact deflation that in turn decreases the accuracy of the reduced-order model. In this talk, we discuss the effects of inexact deflation in projection-based order reduction. We review some of the underlying theoretical results about exact deflation, discuss some practical remedies to minimize the loss of accuracy in the case of inexact deflation, and present results of numerical experiments. We will also consider the special case of structure-preserving order reduction techniques, such as SPRIM, that employ suitably chosen partitionings of the underlying block Krylov subspaces in order to preserve key structures of the original large-scale linear dynamical system.

Furtado, Susana, Centro de Estruturas Lineares e Combinatórias da U. L, Porto, Portugal [CT, Thu. 11:25, Room 3]

Order Invariant Spectral Properties for Several Matrices

The collections of m n-by-n matrices with entries in a field such that the products in any of the m! orders share a common similarity class (resp. spectrum, trace) are studied. The spectral and trace order invariant properties are characterized and the similarity invariant one is related to them in several cases. A complete explicit description is given in case m = 3 and n = 2. (with Charles Johnson)

Furuichi, Shigeru, Nihon University, Tokyo, Japan [CT, Mon. 16:55, Room 4]

On trace inequalities for products of matrices

Skew informations are expressed by the trace of products of matrices and power of matrices. In my talk, we study some matrix trace inequalities of products of matrices and the power of matrices. (with Ken Kuriyama and Kenjiro Yanagi)

Gassó, Maria T., Inst. Mat. Mult. Universidad Politécnica Valencia, Valencia, Spain [CT, Tue. 12:15, Room 3]

The class of Inverse-Positive matrices with checkerboard pattern

In economics as well as other sciences, the inverse-positivity of real square matrices has been an important topic. A nonsingular real matrix A is said to be inverse-positive if all the elements of its inverse are nonnegative. An inverse-positive matrix being also a Z-matrix is a nonsingular M-matrix, so the class of inverse-positive matrices contains the nonsingular M-matrices, which have been widely studied and whose applications, for example, in iterative methods, dynamic systems, economics, mathematical programming, etc, are well known. Of course, every inverse-positive matrix is not an M-matrix. For instance,

A = ( \begin{matrix}−1 & 2 \\ 3 & −1 \end{matrix} )

is an inverse-positive matrix that is not an M-matrix. The concept of inverse-positive is preserved by multiplication, left or right positive diagonal multiplication, positive diagonal similarity and permutation similarity. The problem of characterizing inverse-positive matrices has been extensively dealt with in the literature (see for instance [1]). The interest of this problem arises from the fact that a linear mapping F (x) = Ax from R^{n} into itself is inverse issotone if and only if A is inverse-positive. In particular, this allows us to ensure the existence of a positive solution for linear systems Ax = b for any b ∈ R_{+}^{n}. In this paper we present several matrices that very often occur in relation to systems of linear or nonlinear equations in a wide variety of areas including finite difference methods for contour problems, for partial differential equations, Leontief model of circulating capital without joint production, and Markov processes in probability and statistics. For example, matrices that for size 5 × 5 have the form

A = ( \begin{matrix}1 & −a & 1 & −a & 1 \\ 1 & 1 & −a & 1 & −a \\ −a & 1 & 1 & −a & 1 \\ 1 & −a & 1 & 1 & −a \\ −a & 1 & −a & 1 & 1 \end{matrix} ) ,

where a is a real parameter with economic interpretation. Are these matrices inverse-positive?. We study the answer of this question and we analyze when the concept of inverse-positive is preserved by the Hadamard product A ∘ A^{−1}. In this work we present some conditions in order to obtain new characterizations for inverse-positive matrices. Johnson in [3] studied the possible sign patterns of a matrix which are compatible with inverse-positiveness. Following his results we analyze the inverse-positive concept for a particular type of pattern: the checkerboard pattern. An n × n real matrix A = (a_{i,j}) is said to have a checkerboard pattern if sign(a_{i,j}) = (−1)^{i+j}, i, j = 1, 2, …, n. We study in this paper the inverse-positivity of bidiagonal, tridiagonal and lower (upper) triangular matrices with checkerboard pattern. We obtain characterizations of the inverse-positivity for each class of matrices. Several authors have investigated about the Hadamard product of matrices. Johnson [2] showed that if the sign pattern is properly adjusted the Hadamard product of M-matrices is again an M-matrix and for any pair M,N of M-matrices the Hadamard product M ∘ N^{−1} is again an M-matrix. This result does not hold in general for inverse-positive matrices. We analyze when the Hadamard product M ∘ N^{−1}, for M,N checkerboard pattern inverse-positive matrices, is an inverse-positive matrix.

References

[1] A. Berman, R.J. Plemmons, Nonnegative matrices in the Mathematical Sciences, SIAM 1994.

[2] C.R. Johnson, A Hadamard Product Involving M-matrices, Linear Algebra and its Applications, 4 (1977) 261-264.

[3] C.R. Johnson, Sign patterns of inverse nonnegative matrices, Linear Algebra and its Applications, 55 (1983) 69-80.

(with Manuel F. Abad, and Juan R. Torregrosa)

Gaubert, Stephane, INRIA and CMAP, Ecole Polytechnique, Palaiseau, France [MS7, Mon. 10:45, Room 2]

Using max-plus eigenvalues to bound the roots of a polynomial

A classical problem consists in bounding the modulus of the zeros of a polynomial in terms of the modulus of its coefficients, or, more generally, in bounding the modulus of the eigenvalues of a matrix in terms of the modulus of its entries. We approach this problem using ideas of max-plus or tropical algebra. If p = ∑_{0≤k≤n} a_{k}x^{k} is a polynomial with complex coefficients, we define the tropical roots of p to be the points x ≥ 0 at which the maximum max_{0≤k≤n} |a_{k}|x^{k} is attained at least twice. This definition is natural if one considers the multiplicative version of the max-plus semiring. The tropical roots can be computed by a variant of the Newton polygon construction, in which the usual valuation of a Puiseux series is replaced by the valuation which takes the opposite of the logarithm of the modulus of a complex number. Tropical roots appeared before the tropical era in works of Ostrowski and Pólya on Graeffe’s method, and they were already implicit in a work of Hadamard. We establish log-majorisation inequalities relating the moduli of the roots of a polynomial p and certain tropical roots, up to multiplicative constants depending only on the degree. Our approach relies on matrix arguments, exploiting properties of the tropical analogues of the compound matrix and of the eigenvalues. We show in particular that the maximal circuit mean of the k-th tropical compound of the companion matrix of p is bounded above by the product of the k largest tropical roots of p. We also show that the sequence of the moduli of the eigenvalues of a complex matrix is weakly log-majorised by the sequence of its tropical eigenvalues up to a multiplicative constant depending only on the dimension. We recover along these lines some previous inequalities due to Hadamard, Fujiwara, Specht and Ostrowski, and we also obtain new inequalities. (with Marianne Akian (INRIA) and Adrien Brandejsky (ENS Cachan))

Gavalec, Martin, University of Hradec Králové, Hradec Králové, Czech Republic [MS7, Wed. 11:25, Room 3]

Permuted max-min eigenvector problem

Eigenvectors in extremal algebras are motivated by steady states of discrete events systems whose behaviour is described by a square matrix corresponding to transition from one state of the system to the next state. In the situation when a given state vector is not an eigenvector of the transition matrix, then the system is not stable and we may ask whether it is possible to renumber the inputs so that the system with permuted states becomes stable. The following Permuted Eigenvector problem (PEV) is discussed in this contribution: Given a square matrix A and a vector x of the same dimension in max-min algebra, decide whether there is a permutation π on indices such that the permuted vector x_{π} is an eigenvector of matrix A, i.e A ⊗ x_{π} = x_{π}. Analogous problem has recently been studied by P. Butkovič in [1] for matrices and vectors in max-plus algebra. It has been shown that the max-plus version of PEV is NP-complete and so is IPEV, the restriction of PEV to integer values. Relations of PEV to further notions in max-min algebra, like strongly regular matrix, simple image vector (vector with unique pre-image), generally trapezoidal matrix (see [2, 4]), will be described in the presentation. It will be shown that PSIV, the restriction of PEV to simple image vectors (and consequently, to strongly regular matrices) can be solved in polynomial time using the generally trapezoidal algorithm GenTrap described in [3].

References

[1] P. Butkovič, Permuted max-algebraic (tropical) eigenvector problem is NP-complete, Linear Algebra and its Applications 428 (2008) 1874-1882.

[2] M. Gavalec, J. Plavka, Strong regularity of matrices in general max-min algebra, Linear Algebra and its Applications 371 (2003), 241-254.

[3] M. Gavalec, General trapezoidal algorithm for strongly regular max-min matrices, Linear Algebra and its Applications 369 (2003), 319-338.

[4] M. Gavalec, J. Plavka, Simple image set of linear mappings in a max-min algebra, Discrete Applied Mathematics 155 (2007), 611-622. (with J. Plavka)

Gemignani, Luca, Department of Mathematics University of Pisa, Pisa, Italy [Plenary, Thu. 15:30–16:25]

Eigenvalue Problems for Rank-structured Matrices

A recent significant breakthrough in the field of numerical linear algebra is the design of fast and numerically

stable eigenvalue algorithms for certain classes of rank-structured matrices, including, for instance, diagonal plus low-rank and companion matrices. Our developments in numerical methods for solving these large structured eigenvalue problems are reviewed and state-of-the-art algorithms for both direct and inverse problems are discussed. As well as important conceptual and theoretical aspects, emphasis is also placed on more practical computational issues and applications in matrix and polynomial computations.

Glebsky, Lev, Universidad Autónoma de San Luis Potosi, San Luis Potosi, México [CT, Tue. 11:50, Room 3]

On low rank perturbations of matrices

The talk is devoted to different aspects of the question: “What can be done with a matrix by a low rank perturbation?" It is proved that one can change a geometrically simple spectrum drastically by a rank 1 perturbation, but the situation is quite different if one restricts oneself to normal matrices. Also the Jordan normal form of a perturbed matrix is discussed. It is proved that with respect to the distance d(A, B) = \frac{rank(A−B)}{n} (here n is the size of the matrices) all almost unitary operators are near unitary. (with Luis Manuel Rivera)

Goldberger, Assaf, Tel Aviv University, Tel Aviv, Israel [CT, Fri. 16:20, Room 3]

An upper bound on the characteristic polynomial of a nonnegative matrix leading to a proof of the Boyle–Handleman conjecture

We prove a conjecture by Boyle and Handelam, saying that if A ∈ ℝ^{n,n} is a nonnegative matrix of rank r and spectral radius 1, and if χ_{A}(t) is its characteristic polynomial, then χ_{A}(x) ≤ x^{n} − x^{n−r} for all x ≥ 1. Our proof is based on the Newton Identities. (with Michael Neumann)

Gouveia, María, Department of Mathematics, FCTUC, Coimbra, Portugal [CT, Mon. 16:55, Room 3]

On a singular Toeplitz pencil

The Toeplitz Pencil Conjecture stated by W. Schmale and P.K. Sharma is equivalent to a conjecture for n × n Hankel matrices over ℂ[x]. In this paper it is shown how results on the theory of Hankel matrices over domains can be used to solve this conjecture.

Grout, Jason, Iowa State University, Ames, USA [MS1, Thu. 11:25, Room 1]

Characterizing graphs with minimum rank at most a given number over a finite field using polarities of projective geometries

The structures of all graphs having minimum rank at most k over a finite field with q elements will be characterized for any possible k and q. A strong connection between this characterization and polarities of projective geometries will be explained. Using this connection, a few results in the minimum rank problem will be derived by applying some known results from projective geometry.

Grudsky, Sergey, CINVESTAV del I.P.N., México, México [CT, Mon. 18:35, Room 3]

Uniform boundedness of Toeplitz Matrices with variable coefficients

Uniform boundedness of sequences of variable-coefficient Toeplitz matrices is a surprisingly delicate problem. We show that if the generating function of the sequence belongs to a smoothness scale of the Holder type and if α is the smoothness parameter, then the sequence may be unbounded for α < .05 while it is always bounded for α < .05 Gugercin, Serkan, Virginia Tech, Blacksburg, VA, USA [MS5, Thu. 10:35, Room 2]

A Krylov-Based Descent Approach for the Optimal H_{2} Model Reduction of Large-Scale Dynamical Systems

In this work, we present an approach to model reduction for linear dynamical systems that is numerically stable, computationally tractable even for very large order systems, produces a sequence of monotone decreasing H_{2} error norms, and is globally convergent to a reduced order model that is guaranteed to satisfy first-order optimality conditions with respect to H_{2} error. The interpolation points are the variables of the underlying optimization problem. Convergence properties and effectiveness of the algorithm are presented through numerical examples.

Guo, Chun-Hua, University of Regina, Regina, Canada [MS6, Tue. 11:25, Room 1]

On Newton’s method and Halley’s method for p-th roots of matrices

If A is any matrix with no eigenvalues on the closed negative real axis, the principal pth root of A, A^{1/p} (p ≥ 2 is any integer), can be computed by Newton’s method or Halley’s method (with X_{0} = I) after a proper preprocessing if necessary. The matrix A may also be allowed to have semisimple zero eigenvalues. We show that Newton’s method converges to A^{1/p} if all eigenvalues of A are in {z : |z − 1| ≤ 1} and all zero eigenvalues of A (if any) are semisimple. Suppose that all eigenvalues of A are in {z : |z − 1| < 1} and write A = I − B (so ρ(B) < 1). Let (I − B)^{1/p} = ∑_{i=0}^{∞} c_{i}B^{i} be the binomial expansion. Then the sequence X_{k} generated by Newton’s method or by Halley’s method has the Taylor expansion X_{k} = ∑_{i=0}^{∞} c_{k,i}B^{i}. For Newton’s method we show that c_{k,i} = c_{i} for i = 0, 1, …, 2^{k} −1, and for Halley’s method we show that c_{k,i} = c_{i} for i = 0, 1, …, 3^{k} − 1.

Guzmán, José Ramón, Instituto de Investigaciones Económicas. UNAM., México, México [CT, Fri. 15:30, Room 4]

Reduction of an Ito’s diffusion input output model for the determination of square mean stability

While Ito´ s difussion is known for scientists coming of different areas such as physics, engineering, biology; for social scientists it is practically unknown. In this stochastic process the relevant points to consider are the 1-mean stability (Lyapounov stability) and square mean stability, more strong that 1-mean stability. In particular we propose a multisectoral difussion linear input output model. When considering this dynamical economic system there is associated a differencial equation system with symmetric state variables for the investigation of the square mean stability. Of this last system a d^{2} × d^{2} matrix is obtained. Here is proposed a general algorithm that transforms the d^{2} × d^{2} matrix to one of order ((d(d + 1))/2) ∗ ((d(d + 1))/2), conserving the same eigenvalues information. This reduction algorithm allows us supercomputations of eigenvalues for large scale dynamical input output systems.

Harel, Guershon, Dept of Math, University of California, San Diego, San Diego, USA [MS4, Mon. 10:45, Room 1]

Intellectual Need and Its Role in Mathematics Instruction: Focus on Linear Algebra

The notion of intellectual need is inextricably linked to the notion of epistemological justification. Generally speaking, epistemological justification refers to the learner’s discernment of how and why a particular piece of knowledge came to be. It involves the learner’s perceived cause for the birth of knowledge. The perceived cause is a problematic situation whose resolution for the learner has necessitated for her or him the creation of a new knowledge. Such a situation is called intellectual need. Most students, even those who desire to succeed in school, are intellectually aimless in mathematics classes because their teachers fail to help them realize an intellectual need for what they intent to teach them. In this talk I will discuss the role these two constructs should play in mathematics instruction, focusing mainly on the learning and teaching of linear algebra.

Hershkowitz, Danny, Technion, Haifa, Israel [MS1, Wed. 11:00, Room 1]

On nonnegative sign equivalent and sign similar factorizations of matrices

It is shown that every real n × n matrix is a product of at most two nonnegative sign equivalent matrices, and every real n × n matrix, n=2, is a product of at most three nonnegative sign similar matrices. Finally, it is proved that every real n × n matrix is a product of totally positive sign equivalent matrices. However, the question of the minimal number of such factors is left open. (with Allan Pinkus)

Hnětynková, Iveta, Dep. of Mathematics, Arizona State University, Tempe, Arizona [MS3, Thu. 18:10, Room 2]

On solvability of total least squares problem

Let A be a real m by n matrix, and b a real m-vector. Consider estimating x from an orthogonally invariant linear approximation problem

Ax ≈ b,  (15)

where the data b, A contain redundant and/or irrelevant information. In total least squares (TLS) this problem is solved by constructing a minimal correction to the vector b and the matrix A such that the corrected system is compatible. Contrary to the standard least squares approximation problem, a solution of a TLS problem does not always exist. In addition, the data b, A can suffer from multiplicities and in this case a TLS solution may not be unique. Classical analysis of TLS problems is based on the so called Golub - Van Loan condition σ_{min}(A) > σ_{min}([b, A]) , see [2, 4]. This condition is, however, intricate through the fact that it is only sufficient but not necessary for the existence of a TLS solution. A new contribution to the theory and computation of linear approximation problems was published in a sequence of papers [5, 6, 7], see also [3]. Here it is proved that the partial upper bidiagonalization [1] of the extended matrix [b, A] determines a core approximation problem A_{11}x_{1} ≈ b_{1} , with the necessary and sufficient information for solving the original problem given by b_{1} and A_{11}. The transformed data b_{1} and A_{11} can be computed either directly, using Householder orthogonal transformations, or iteratively, using the Golub-Kahan bidiagonalization. It is shown how the core problem can be used in a simple and efficient way for solving the total least squares formulation of the original approximation problem.

In this contribution we discuss the necessary and sufficient condition for the existence of a TLS solution based on the core reduction, and mention work on extensions of the results to linear approximation problems with multiple right hand sides [8].

References

[1] G. H. Golub, W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, SIAM J. Numer. Anal. Ser. B 2, pp. 205–224, 1965.

[2] G. H. Golub, C. F. Van Loan, An analysis of the total least squares problem, SIAM J. Numer. Anal. 17, pp. 883–893, 1980.

[3] I. Hnětynková, Z. Strakoš, Lanczos tridiagonalization and core problems, Lin. Alg. Appl. 421, pp. 243–251, 2007.

[4] S. Van Huffel, J. Vandewalle, The total least squares problem: computational aspects and analysis, SIAM, Philadelphia, 1991.

[5] C. C. Paige, Z. Strakoš, Scaled total least squares fundamentals, Numer. Math. 91, pp. 117–146, 2002.

[6] C. C. Paige, Z. Strakoš, Unifying least squares, total least squares and data least squares, in “Total Least Squares and Errors-in-Variables Modeling”, S. van Huffel and P. Lemmerling, editors, Kluwer Academic Publishers, Dordrecht, pp. 25–34, 2002.

[7] C. Paige, Z. Strakoš, Core problems in linear algebraic systems, SIAM J. Matrix Anal. Appl. 27, pp. 861–875, 2006.

[8] I. Hnětynková, M. Plešinger, D. M. Sima, Z. Strakoš, S. Van Huffel, The total least squares problem and reduction of data in AX ≈ B, in preparation.

(with Z. Strakoš and M. Plešinger)

Hogben, Leslie, Iowa State University, Ames, Iowa, USA [Plenary, Mon. 8:20–9:15]

Minimum Rank Problems: Recent Developments

This talk will survey recent developments in the problem of determining the minimum rank of families of

matrices described by a graph, digraph or pattern.

Horn, Roger, University of Utah, Salt Lake City, USA [CT, Mon. 12:00, Room 3]

A Canonical Form for Quasi-Real Normal Matrices Under Real Orthogonal Similarity

A square complex matrix A is quasi-real normal (QRN) if (a) it is normal, (b) the conjugate of every eigenvector is an eigenvector (possibly with a different eigenvalue), and (c) its null space is self conjugate. We show that A is QRN if and only if it is normal and either it commutes with its conjugate or it commutes with its transpose (each implies the other). The class of QRN matrices is closed under the equivalence relation of real orthogonal similarity, which is simultaneously a similarity, a unitary ^{∗}congruence, and a unitary ^{T} congruence. We give a block diagonal canonical form for QRN matrices under this equivalence relation. (with Geoffrey R. Goodson)

Iannazzo, Bruno, Dipto. di Fisica e Mat., Università dell’Insubria, Como, Italy [MS6, Tue. 11:50, Room 1]

Matrix iterations for matrix functions

Matrix functions od the type f(A), where f is some complex function and A is a square matrix, are often computed by matrix fixed-point iterations. These iterations are of the form X_{k+1} = φ(X_{k}), where φ may depend on A. We show how the convergence of a matrix iteration is related to the convergence of the same iteration applied to the eigenvalues of A and we discuss the local convergence from which the numerical stability of the iteration strongly depends. We consider some specific examples regarding the matrix pth root.

Im, Bokhee, Chonnam National University, Gwangju, Korea(Rep. of) [CT, Thu. 11:00, Room 5]

Representations of trilinear products in Comtrans algebras

Unlike the set of all Lie algebras, the set of all comtrans algebras on a given module has a linear structure. Let E be a finite-dimensional vector space over a field k. Then we want to determine which trilinear products xyz on E may be represented as linear combinations of the commutator and translator of a comtrans algebra on E in the manner of the following so-called bogus product:

xyz = \frac{1}{6}[x, y, z] + \frac{1}{6}[y, z, x] + \frac{1}{6}[z, x, y] + \frac{1}{3}⟨x, y, z⟩ − \frac{1}{3}⟨z, x, y⟩.

If the underlying field is not of characteristic 3, then we show that the necessary and sufficient condition for such a representation is

xxy + xyx + yxx = 0 ,

a condition described as strong alternativity. Indeed, if the underlying field is also not of characteristic 2, then each strongly alternative trilinear product is represented as the bogus product of a comtrans algebra. An appropriate representation for the case of characteristic 2 will also be given. (with Jonathan D. H. Smith)

Jiang, Er-Xiong, Shanghai University, Shanghai, China [Plenary, Mon. 9:20–10:15]

Some inverse eigenvalue problems for Jacobi matrices

Let

T_{1,n} = ( \begin{matrix}α_{1} & β_{1} \\ β_{1} & α_{2} & ... & 0 \\ & ... & ... & ... \\ ... & ... & β_{n−1} \\ 0 & β_{n−1} & α_{n} \end{matrix} ) .

Denote

T_{p,q} = ( \begin{matrix}α_{p} & β_{p} & & & 0 \\ β_{p} & α_{p+1} & β_{p+1} \\ & β_{p+1} & ... & ... \\ & & ... & ... & β_{q−1} \\ 0 & & & β_{q−1} & α_{q} \end{matrix} ) (p < q ≤ n.)

If all β_{i} > 0 i = 1, 2, ..., n − 1,we call T_{1,n} a Jacobi matrix.

The following 3 kinds of inverse eigenvalue problem for Jacobi matrices will be discussed

1.(K) problem [1], [2]: Given 3 sets of real numbers {λ_{1}, λ_{2}, ..., λ_{n}}, {μ_{1}, μ_{2}, ..., μ_{k−1}}, {μ_{k}, μ_{k+1}, ..., μ_{n−1}}, find a n × n Jacobi matrix T_{1,n},such that λ_{1}, λ_{2}, ..., λ_{n} are eigenvalues of T_{1,n},μ_{1}, μ_{2}, ..., μ_{k−1} are eigenvalues of T_{1,k−1} and μ_{k}, μ_{k+1}, ..., μ_{n−1} are the eigenvalues of T_{k+1,n}.

2. Double dimension problem [3] [4] [5] [6]: given a Jacobi matrix T_{1,n}and given 2n real numbers {λ_{1}, λ_{2}, ..., λ_{2n}}, find a 2n × 2n Jacobi matrix T_{1,2n}, such that T_{1,n} is a leading principal submatrix of T_{1,2n} and λ_{1}, λ_{2}, ..., λ_{2n} are the eigenvalues of T_{1,2n}.

A periodic Jacobi matrix is an n × n real symmetric matrix of the form

J_{n} = ( \begin{matrix}α_{1} & β_{1} & & & & β_{n} \\ β_{1} & α_{2} & β_{2} & & & 0 \\ 0 & β_{2} & α_{3} & ... & & 0 \\ ⋮ & & ... & ... & ... & ⋮ \\ 0 & & & ... & α_{n−1} & β_{n−1} \\ β_{n} & 0 & ⋯ & 0 & β_{n−1} & α_{n} \end{matrix} ) .

where β_{i} > 0, i = 1, 2, ..., n.

3. Periodic problem [4] [5], [7]: Given two sets of real numbers {λ_{1}, λ_{2}, ..., λ_{n}} and {μ_{1}, μ_{2}, ..., μ_{n−1}},find a n × n periodic Jacobi matrix J_{n},such that λ_{1}, λ_{2}, ..., λ_{n} are the eigenvalues of J_{n} and μ_{1}, μ_{2}, ..., μ_{n−1} are the eigenvalues of T_{1,n−1} which is the (n − 1) × (n − 1)leading principal submatix of J_{n}

References

[1] G. M. Gladwell and N. B. Willms, The reconstruction of a tridiagonal system from its frequency respose at an interior point, Inverse Problems, 4, 1988, pp.1013-1024.

[2] Er-Xiong Jiang, An inverse eigenvalue problem for Jacobi matrices, J. Comput. Math. 21, 2003, pp.569-584.

[3] H. Hochstadt, On the Construction of a Jacobi Matrix from Mixed Given Data, Linear Algebra and Its Appl., 28, 1979, pp. 113-115.

[4] S. F. Xu,An Introduction to Inverse Algebraic Eigenvalue Problems, Peking University Press, Beijing, 1998.

[5] D. Boley and G.H. Golub, A survey of matrix inverse eigenvalue problems, Inverse Problems 3,pp.395-622,1987.

[6] Hai-xia Liang, Er-xiong Jiang, An inverse eigenvalue problem for Jacobi matrices, J. Comput. Math. Vol.25, No.5,2007,pp.620-630.

[7] Yinghong Xu, Er-xiong Jiang, An inverse eigenvalue problem for periodic Jacobi matrices, Inverse problems, 23, 2007, pp. 165-181.

Karow, Michael, Technische Universitat, Berlin, Germany [MS2, Fri. 11:50, Room 1]

Pseudospectra and Stability radii for Hamiltonian Matrices

We consider the variation of the spectrum of Hamiltonian matrices under Hamiltonian perturbations. The first part of the talk deals with the associated structured pseudospectra. We show how to compute these sets and give some examples. In the second part we discuss the robustness of linear stability. In particular we determine the smallest norm of a perturbation that makes the perturbed Hamiltonian matrix unstable.

Kirkland, Steve, University of Regina, Regina, Canada [MS1, Wed. 11:25, Room 1]

Constructing Laplacian Integral Split Graphs

Given a graph G, its Laplacian matrix, L, is defined as L = D − A, where A is the (0, 1) adjacency matrix for G, and D is the diagonal matrix of vertex degrees. A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. A split graph is one whose vertex set can be partitioned as A ∪ B, where A induces a clique and B induces an independent set of vertices. Merris has posed the problem of identifying and/or constructing Laplacian integral split graphs. Using balanced incomplete block designs, Diophantine equations, and Kroneker products, we describe a technique for constructing infinite families of Laplacian integral split graphs, thus partially addressing the problem posed by Merris. (with N. Abreu, M. de Freitas and R. Del Vecchio)

Klasa-Bompoint, Jacqueline, Dawson College, Montreal, Canada [MS4, Tue. 16:55, Room 1]

Few pedagogical scenarios in Linear Algebra with Cabri and Maple

With the appearance of very rapidly improving technologies, since the 90’s we have faced many reform movements introducing much more importance on the visualization of mathematical concepts together with more socialization (Collaborative learning). Just to name few reform groups in the USA: Harvard Group for Calculus and for Linear algebra: ATLAST organized by S. Leon after the ILAS symposium of 1992 and LACSG started with D. Lay in 1990 and then continued with D. Carlson (1993) and many others. However some researchers like J.P Dorier and A. Sierpinska were not optimist and declared “It is commonly claimed in the discussions about the teaching and learning of linear algebra, that linear algebra courses are badly designed and badly taught and that no matter how it is taught, linear algebra remains a cognitively and conceptually difficult subject". On the other hand, M. Artigue advocates strongly the use of CAS’s but with a constant awareness that Mathematics learned in such an environment of software are changing. How do we really teach Linear algebra now? See the standard Anton’s text book and then the much praised book “Linear Algebra and its applications" written in 1994 by D. Lay. How hard is it really now to teach and to learn this topic? We shall repeat like J. Hillel, A. Sierpinska and T. Dreyfus that the teaching of Linear Algebra offers to students many cognitive problems related to three thinking modes intertwined: geometric, computational (with matrices) and algebraic (Symbolic). We could follow the APOS theory of E. Dubinsky and see that it will be necessary for the teacher to proceed to a genetic decomposition of every mathematical concept of Linear Algebra before being able to conceive a pedagogic scenario that will have to bring students from the “action" to the more elaborated state of “process" and then luckily make them reach the most abstract levels of “objects" and even higher structured “schemes". While devising my classes and computer-labs to my students in Linear Algebra, I was inspired by all good ideas presented by the mentioned authors and many others as: G. Bagni, J.L. Dorier and Fischbein, D. Gentner, G. Harel, J. Hillel, J.G. Molina Zavaleta. I am a mathematician who teaches in a CEGEP, which is a special college of Québec’s province in Canada. Pedagogical scenarios based on Cabri and Maple will be presented in this study for some few stumbling blocks in the learning of Linear Algebra: linear transformations, eigenvectors and eigenvalues, quadratic forms and conics with changes of bases, finally singular values. When immersed in this software environment, I restrict all the demonstrations to R^{2} and R^{3}. Can visualization and manipulation improve and facilitate the learning of Linear algebra? As I am biased, of course I will say yes; really we would need a strong evaluation and analysis of this teaching procedure to be able to give answers. As Ed. Dubinsky would say “This situation provides us with the opportunity to build a synthesis between the abstract and concrete." The interplay between concrete phenomena and abstract thinking." I will add also, that students working in teams around computers (or even graphic calculators) only coached by the teacher at times, become experts in the discipline they experiment with. About the roles of the CAS Maple and the geometrical software, we will agree with the Cabrilog slogan “Cabri makes tough maths concepts easier to learn thanks to its kinaesthetic learning approach!" while Maple acts like a good big brother, doing all the boring calculations for the students and also producing instructive animations, unfortunately mostly programmed by the teacher.

Klein, Andre, University of Amsterdam, Amsterdam, The Netherlands [MS6, Tue. 12:15, Room 1]

Tensor Sylvester matrices and information matrices of multiple stationary processes

Consider the matrix polynomials A(z) and B(z) given by

A(z) = ∑_{j=0}^{p} A_{j}z^{j}

and

B(z) = ∑_{j=0}^{q} B_{j}z^{j},

where A_{0} ≡ B_{0} ≡ I_{n}.

Gohberg and Lerer [1] study the resultant property of the tensor Sylvester matrix

S^{⊗}(−B, A) ≜ S(−B ⊗ I_{n}, I_{n} ⊗ A)

or

S^{⊗}(−B, A) = ( \begin{matrix}(−I_{n}) ⊗ I_{n} & (−B_{1}) ⊗ I_{n} & ⋯ & (−B_{q}) ⊗ I_{n} & 0_{n^{2}×n^{2}} & ⋯ & 0_{n^{2}×n^{2}} \\ 0_{n^{2}×n^{2}} & ... & ... & & ... & ... & ⋮ \\ ⋮ & ... & ... & ... & & ... & 0_{n^{2}×n^{2}} \\ 0_{n^{2}×n^{2}} & ⋯ & 0_{n^{2}×n^{2}} & (−I_{n}) ⊗ I_{n} & (−B_{1}) ⊗ I_{n} & ⋯ & (−B_{q}) ⊗ I_{n} \\ I_{n} ⊗ I_{n} & I_{n} ⊗ A_{1} & ⋯ & I_{n} ⊗ A_{p} & 0_{n^{2}×n^{2}} & ⋯ & 0_{n^{2}×n^{2}} \\ 0_{n^{2}×n^{2}} & ... & ... & & ... & ... & ⋮ \\ ⋮ & ... & ... & ... & & ... & 0_{n^{2}×n^{2}} \\ 0_{n^{2}×n^{2}} & ⋯ & 0_{n^{2}×n^{2}} & I_{n} ⊗ I_{n} & I_{n} ⊗ A_{1} & ⋯ & I_{n} ⊗ A_{p} \end{matrix} )

.

In [1] it is proved that the matrix polynomials A(z) and B(z) have at least one common eigenvalue if and only if detS^{⊗}(−B, A) = 0 or when the matrix S^{⊗}(−B, A) is singular. In other words, the tensor Sylvester matrix S^{⊗}(−B, A) becomes singular if and only if the scalar polynomials det A(z) = 0 and det B(z) = 0 have at least one common root. Consequently, it is a multiple resultant. In [2], this property is extended to the Fisher information matrix of a stationary vector autoregressive and moving average process, VARMA process. The purpose of this talk consists of displaying a representation of the Fisher information matrix of a stationary VARMAX process in terms of tensor Sylvester matrices, the X stands for exogenous or control variable. The VARMAX process is of common use in stochastic systems and control.

Kopparty, Bhaskara Rao, Indiana State University, Terre Haute, IN, USA [CT, Mon. 18:10, Room 2]

Generalized inverses of infinite matrices

We pose several problems about generalized inverses of infinite matrices. We shall review the literature and prove some positive results.

Körtesi, Peter, University of Miskolc, Miskolc, Hungary [CT, Thu. 10:35, Room 5]

Using Linear Algebra in Teaching Hamilton Quaternions and Graphs

Hamilton quaternions are usually introduced as generalization of complex numbers respecting the basic identities. We present a way to use matrices to introduce quaternions and study their properties, using an isomorphism between the two skew-field structures. The Eulerian and Hamiltonian trails and circuits can be described as well using some adjacency type matrices in special rings. The method to be presented is the same time a sufficient condition to decide weather the graph is Hamiltonian or not.

Kressner, Daniel, ETH Zurich, Zurich, Switzerland [Plenary, Tue. 9:10–10:05]

Matrix product eigenvalue problems

In its simplest form, the product eigenvalue problem consists of determining the eigenvalues and eigenvectors of a matrix product

Π = A_{p}A_{p−1} ⋯ A_{1}

with n × n matrices A_{k}. The most general form is obtained by admitting rectangular as well as inverted factors.

The aim of this talk is to provide an overview of theoretical and numerical developments for such eigenvalue problems.

On the theoretical side, we first relate existing canonical forms to the Kronecker-Weierstrass form of an embedded pn×pn block cyclic matrix pencil. This embedding also allows to derive various eigenvalue/eigenvector perturbation results in a convenient and elegant manner. In particular, it is shown that an appropriate extension of pseudospectra to matrix products poses seemingly intractable computational challenges.

On the numerical side, we mainly focus on QR and Krylov subspace type methods. The main issue is to formulate the method in such a way that the explicit computation of the matrix product or parts thereof is completely avoided. The periodic QR algorithm is such a method, suitable for products with medium-sized dense factors. Novel pre- and post-processing steps are presented that admit (a) the treatment of rectangular factors, and (b) the efficient computation of invariant subspaces. For products with large-sized factors, a variant of the implicitly restarted Arnoldi algorithm is presented.

Based on the presented results, a Fortran 77/Matlab software package for solving product eigenvalue problems is being developed. Matlab’s operator overloading facilities lead to a particularly convenient user interface for dealing with matrix products.

This is partly joint work with Robert Granat and Bo Kågström, Umeå University.

Laffey, Thomas, University College Dublin, Dublin, Ireland [MS8, Mon. 17:45, Room 1]

Some constructive techniques in the nonnegative inverse eigenvalue problem

Let σ := (λ_{1}, ... , λ_{n}) be a list of complex numbers and let

s_{k} := λ_{1}^{k} + ... + λ_{n}^{k}, k = 1, 2, 3, ...

be the associated Newton power sums. A famous result of Boyle and Handelman states that if all the s_{k} are positive, then there exists a nonnegative integer N such that

σ_{N} := (λ_{1}, ... , λ_{n}, 0, ... , 0), (N zeros)

is the spectrum of a nonnegative (n + N) × (n + N) matrix A. The problem of obtaining a constructive proof of this result with an effective bound on the minimum number N of zeros required has not yet been solved.

We present a number of techniques for constructing nonnegative matrices with given nonzero spectrum σ, and use them to obtain new upper bounds on the minimal size of such an A, for various classes of σ. This is joint work with Helena Smigoc. (with Šmigoc, Helena)

Lancaster, Peter, University of Calgary, Calgary, Canada [MS6, Tue. 16:55, Room 2]

Linearization of Matrix Polynomials

A precise form will be given to the notion of linearization of matrix polynomials, with special reference to the notion of an eigenvalue at infinity. This will be illustrated with linearizations of matrix polynomials when represented in various polynomial bases; orthogonal and otherwise. This is a report on collaborative work with A. Amiraslani(University of Calgary) and R.W. Corless (University of Western Ontario). (with A. Amiraslani and R.W. Corless)

Lee, Gue Myung, Pukyong National University, Busan, Korea [CT, Thu. 18:35, Room 4]

Complexity Analysis of the Primal-Dual Interior Point Method for Second-order Cone Optimization Problem

The purpose of this talk is to extend the Bai et al.’s complexity results for a linear program to a second-order cone optimization (SOCO) problem. We define a proximity function for SOCO by a kernel function introduced by Bai et al. [SIAM J. Optim., 13(2003), 766-782] and using the proximity function, we formulate an algorithm for a large-update primal-dual interior-point method (IPM) for SOCO and give its complexity analysis, and then we show that the worst-case iteration bound for our IPM is O(\sqrt{N} log N log \frac{N}{ϵ}). (with Bo Kyung Choi)

Lee, Hosoo, Kyungpook National University, Daegu, Korea [CT, Mon. 18:35, Room 4]

Contractions and nonlinear matrix equations on positive definite cones

In this talk we consider the semigroup generated by the self-maps on the open convex cone of positive definite matrices of translations, congruence transformations and matrix inversion that includes symplectic Hamiltonians and show that every member of the semigroup contracts any invariant metric distance inherited from a symmetric gauge function. This extends results of Bougerol for the Riemannian metric and of Liverani-Wojtkowski for the Thompson part mertic. A uniform upper bound of the Lipschitz contraction constant for a member of the semigroup is given in terms of the minimum eigenvalues of its determining matrices. We apply this result to a variety of nonlinear equations including Stein and Riccati equations for uniqueness and existence of positive definite solutions and find a new convergence analysis of iterative algorithms for the positive definite solution depending only on the least contraction coefficient for the invariant metric from the spectral norm. (with Yongdo Lim)

Leon, Steven, University of Massachusetts Dartmouth, Dartmouth, MA 02747, USA [MS4, Tue. 17:20, Room 1]

When MATLAB Gives "Wrong" Answers

One of the main differences between teaching the standard linear algebra course and a course in numerical linear algebra is that in the latter course all computations are done using finite precision arithmetic. One way to illustrate the importance of this difference is to look at examples where computational software packages such as MATLAB appear to be giving wrong answers. In this talk we examine four or five such scenarios. In each case we look at examples and explain how and why MATLAB arrives at its answers. In our final example we examine a MATLAB program that clearly produces an impossible answer. In this case, when the author of the program tried to debug it by printing out intermediate results, the value of the computed solution changed. What is going on? Is MATLAB exhibiting some sort of Heisenberg effect? All will be explained at the talk.

Li, Chi-Kwong, College of William and Mary, Williamsburg, USA [MS2, Fri. 11:25, Room 1]

Eigenvalues of the sum of matrices from unitary similarity orbits

Let A and B be n × n complex matrices. Characterization is given for the set E(A, B) of eigenvalues of matrices of the form U^{∗}AU + V^{∗}BV for some unitary matrices U and V. Consequences of the results are discussed and computer algorithms and programs are designed to generate the set E(A, B). The results refine those of Wielandt on normal matrices. Extensions of the results to the sum of matrices from three or more unitary similarity orbits are also considered. (with Yiu-Tung poon and Nung-Sing Sze)

Loiseau, Jean Jacques, IRCCyN-CNRS, Nantes, France [MS7, Wed. 11:00, Room 3]

Robust stability of positive difference equations

We consider the system of difference equations

x(t) = ∑_{k=1}^{ν} a_{k}x(t − β_{k}),

where a_{k} ∈ ℝ, β_{k} ∈ ℝ, for k = 1 to ν. We assume that the delays are in increasing order, 0 = β_{0} < β_{1} < β_{2} < … < β_{ν}. Such equation appear as models in biology, economy, and from the wave equation (see [3] for examples). The stability of this system was addressed in the references [1–4]. They provide a complete analysis, and point out a very special phenomenon, that the zeros of the characteristic equation

1 − ∑_{k=1}^{ν} a_{k}e^{−β_{k}s} = 0 ,

where s ∈ ℂ, do not continuously depend on the parameters β_{k}. The result is that, if the delays are rationally independant, the system is stable (both in the sense of L_{2}–stability and of expenential stability) if and only the following holds

∑_{k=1}^{ν} |a_{k}| < 1 .

At the contrary, when the delays are rationally dependent, this condition is sufficient for the stability, but not necessary. The rational dependance of the coefficients is not a continuous property, which somehow explains what happens. As a typical example, one can check that the system

x(t) = \frac{3}{4}x(t − 1) − \frac{3}{4}x(t − 2)

is stable. But, since 3/4 + 3/4 > 1, one can see that the stability is lost by arbitrary little perturbations of the delays. Almost all the systems of the form

x(t) = \frac{3}{4}x(t − 1) − \frac{3}{4}x(t − 2 − ϵ) ,

are unstable, for example ϵ = π/100 gives an unstable system. Two remarks can now be done. The first one is that Max-plus linear systems are also difference equations. Such systems are obtained as algebraic models of timed marked graphs, a special class of Petri nets, where the delays are associated to the edges of an oriented graph, they correspond to the minimal time to cross this edges. As it is well known (see for instance [5] or [6]), the asymptotic behaviour of such a graph is given by the eigenvalue, in the Max-Plus sence, of the corresponding matrix. This eigenvalue can be expressed analitically as the maximum mean weight of the elementary circuits of the graph. This quantity depends continuously on the parameters of the graph, that are the delays and some coefficients called initial marks. The asymptotic behaviour of Max-Plus linear systems do not depend on the algebraic dependance of the delays, at the contrary of usual difference equations. Our second remark, which now follows, in some sense explains that the difference of behaviour between Max-Plus systems and usual difference equations is not a paradox. In many applications, the coefficients a_{k} of our basic equation are positive. Hence the considered equation is called a positive difference equation. We can show that the zeros of the characteristic equation of a positive difference equation continuously depends on the parameters a_{k} and β_{k}. In particular for these systems too, the algebraic dependance of the delays does not the matter, and in every case the system is stable if and only if the condition above is satisfied, the sum of the coefficients a_{k} is less than 1. Since the condition is not delay dependant, it is independant to variations of the delay, and one therefore says that the stability is robust. To show this result, we denote μ the unique real root of the equation

1 − ∑_{k=1}^{ν} a_{k}e^{−β_{k}μ} .

As shown in [2], μ is an upper bound of the real parts of the zeros of the above characteristic equation. If in addition the coefficients a_{k} are positive, one can show that μ is a zero of the characteristic equation, which leads to the conclusion. Thanks to Perron-Frobenius theorem, a similar result can be described in the case of multivariable positive difference equations.

[1] D. Henry, Linear autonomous neutral functional differential equations, J. Differential equations, vol.15, 106-128, 1974.

[2] C. E. Avellar and J. K. Hale, On the zeros of exponentials polynomials, Journal of Mathematical Analysis and Applications, vol. 73, 434-452, 1980.

[3] V. Kolmanovski and V.R. Nosov, Stability of functional differential equations, Academic Press, London, 1986.

[4] J.K. Hale and S.M. Verduyn Lunel, Introduction to functional differential equations, Springer Verlag, New York, 1993.

[5] M. Gondran, M. Minoux and S. Vajda, Graphs and Algorithms, John Wiley and Sons, 1984.

[6] F. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat. Synchronization and Linearity. An Algebra for Discrete Event Systems. Wiley, 1992. (with M. Di Loreto)

Machado, Silvia, Pontificia Universidade Catolica de São Paulo, São Paulo, Brasil [CT, Mon. 16:55, Room 2]

GPEA’s researches about the meta resources in teaching and learning the notion of basis of a vector space

Since the late 90’s we have been researching the development of the notion of basis of a vector space in our first Linear Algebra course. This concept was chosen to be explored in our investigations because it has an essential role in this theme. Robert e Robinet (1993) name meta mathematics something that is said or written when information is given about the mathematical functioning and the use of its concepts, that is when we talk ABOUT Mathematics, beyond the strictly mathematical. To avoid confusion about the meaning of the term meta mathematics, utilized in Literature under different meanings, we adopted the term meta resources to design what the authors call meta mathematics. A meta resource can became a lever to the student when he is learning about a mathematical notion. When a meta resource is capable of becoming a lever to the understanding of the desired mathematical concept, Robert and Robinet call it meta lever. We should also highlight the importance given by Dorier (1997) to this resource when he suggests that one of the most important axis to be investigated in the learning and teaching of Linear Algebra is about the use of meta lever and about the evaluation of its real effects on learning. We interpret the teacher’s speech or the presentation of a theme in the textbook, as meta lever, in cases when there are information in it able to make the student think about his own knowledge, his mistakes, his procedures, helping him to understand a new mathematical notion. We consider not only the teacher’s speech, but also any activity proposed and/or elaborated by him, that favors the students’ comprehension about a notion or a topic, such as meta lever. Some papers written seeking to answer the question —What is the role of the meta resources in the learning of the notion of basis in Linear Algebra?— are next. Considering the statement made by Chevallard (1991) about the lack of the teacher’s influence on didactics transposition, Behaj and Arsac (1998) wrote a paper where they discussed the size of the influence that different Algebra teachers have on didactics transposition in their courses. The conclusion of this paper contested Chevallard’s statement by showing that each teacher has his point of view on the best way to write a learning text, what brings differences even between two courses that follow the same (teaching) plan. (BEHAJ, A ARSAC, G., p. 362). This investigation and the analysis made by the authors revealed that each teacher’s autonomy (to prepare the class and to develop them) changes according to the amount of dependence of the textbook and to his research activities. Knowing that not every university teacher researches Algebra-related subjects and that many of them only use textbooks, Araújo (2002) analyzed the development of the basis notion in three of the most utilized textbooks in traditional universities. The author came to the conclusion that there are few meta resources able to become meta levers to the student in those books. BEHAJ and ARSAC’s considerations about the teacher’s interference in didactical transposition suggested that Padredi (2003) investigated which meta resources about basis emerge from the 6 interviewed Algebra teachers’ speech. Padredi utilized three principles that Harel (2000) considers necessary to learn and teach Linear Algebra to elaborate the script and to analyze the interviews. Those principles are those of concreteness, necessity and generalizibility. The author discovered that the teachers showed many meta resources able to become meta lever when learning basis notion. Barbosa de Oliveira (2005), facing the statement above, observed the classes of a Linear Algebra teacher lightening the meta resources utilized in the development of the basis notion and checking, by using interviews, with which students of their class they became meta levers. This way, the researches already finished and the ones still in process point some results that evidence the role of the meta resources in learning the basis notion in Linear Algebra. References ARAUJO, C. V. B. A meta matemática no livro didático de Álgebra Linear. Dissertação de Mestrado (Programa de Educação Matemática) : Pontifícia Universidade Católica de São Paulo. 2002. BARBOSA de OLIVEIRA, L.C. Como funcionam os recursos meta em aula de Álgebra Linear? Dissertação de Mestrado (Programa de Educação Matemática) : Pontifícia Universidade Católica de São Paulo. 2005. BEHAJ, A.; ARSAC, G La conception d’un cours d’Algèbre Linèaire . Recherches en Didactique des Mathématiques, v.18, n^{o} 3, pp. 333-370, 1998. CHEVALLARD, Y. La transposition didactique, du savoir savant au savoir enseigné. Reed. 1991. La Pensée Sauvage. Grenoble. 1991.

DORIER, J. L. L’Enseignement de L’Algebre Linéaire en Question. La Pensée Sauvage. Grenoble. 1997. HAREL, G. Three Principles of Learning and Teaching Mathematics, Chapter 5, On the Teaching of Linear Algebra. Ed. DORIER. Kluwer. 2000. PADREDI, Z.L.N. As alavancas meta no discurso do professor de Algebra Linear. Dissertação de Mestrado (Programa de Educação Matemática) : Pontifícia Universidade Católica de São Paulo. 2002. ROBERT, A.; ROBINET, J. Prise en compte du meta en didactique des Mathématiques. In Cahier DIDIREM. V.21, Ed. IREM. Paris. 1993. (with Bianchini, B. L. and Maranhão, M. C. S. A.)

Maracci, Mirko, Dept of Mathematics and CSCI, Siena University, Siena, Italy [MS4, Mon. 11:35, Room 1]

Basic notions of Vector Space Theory: students’ models and conceptions

Carlson (1993) uses the image of the fog rolling in to describe the confusion and disorientation which his students experience when getting to the basic notions of Vector Space Theory (VST). There is truly a widespread sense of the inadequacy of the teaching of Linear Algebra. On account of that common perception and of the importance of Linear Algebra as a prerequisite for a number of disciplines (math, science, engineering,...), in the last twenty years several studies were carried out on Linear Algebra education. Those studies brought undeniable progresses for understanding students’ difficulties in Linear Algebra. As Dorier and Sierpinska effectively synthesized in their literature survey (2001), three different kinds of sources of students’ difficulties in Linear Algebra especially emerge from the studies on that topics:

1. the fact that Linear Algebra teaching is characterized by an axiomatic approach, which is perceived by students as superfluous and meaningless;

2. the fact that Linear Algebra is characterized by the cohabitation of different languages, systems of representations, modes of description;

3. the fact that coping with those features requires the development of theoretical thinking and cognitive flexibility

Recently more studies were carried out, which in our opinion still fit well Dorier and Sierpinska’s synthesis. In this talk I will focus on some aspects of students’ difficulties in vector space theory (VST), drawn from my doctorate research project. That project was meant to investigate graduate and undergraduate students’ errors and difficulties in VST. Through that work I intended to contribute to Linear Algebra Education research field, focusing on cognitive difficulties related to specific VST notions rather than to general features of Linear Algebra: a seemingly less explored path. The study involved 15 (graduate or undergraduate) students in mathematics, presented with two or three different VST problems to be solved in individual sessions. The methodology adopted was that of the clinical interview (Ginsburg, 1981). The study highlighted a number of students’ difficulties related to the notions of linear combination, linear dependence/independence, dimension and spanning set. The difficults, errors and empasses emerged were analysed through the lenses of different theoretical frameworks: the theory of tacit intuive models (Fischbein, 1987), Sfard’s process-object duality theory (Sfard, 1991) and the ckc model (Balacheff, 1995). The different analyses lead to formulate hypotheses, which account for a variety of students’ difficulties. Though not antithetical to each other, those analyses are diversified, put into evidence different aspects from different perspectives. In this talk I briefly present the results of those analyses and a first tentative integrating analysis, combining different hints and perspectives provided by the frameworks mentioned above. More specifically, that attempt lead to the formulation of the hypothesis that many difficults experienced by students are consistent with the possible activation of an intuitive model of “construction" related to basic notion of VST. In the talk we will better specify that hypothesis showing how it could contribute to better organize and explain students’ documented difficulties.

Balacheff N., 1995; Conception, connaissance et concept, Grenier D. (ed.) Didactique et technologies cognitives en mathématiques, séminaires 1994-1995, pp. 219-244, Grenoble: Université Joseph Fourier.

Carlson D., 1993; Teaching linear algebra: must the fog always roll in?, College Mathematics Journal, vol. 24, n. 1; pp. 29-40.

Dorier J.-L., Sierpinska A., 2001; Research into the teaching and learning of linear algebra, Holton D. (ed.) The Teaching and Learning in Mathematics at University Level- An ICMI Study, Kluwer Acad. Publ., The Netherlands, pp. 255-273.

Fischbein E., 1987; Intuition in science and mathematics, D. Reidel Publishing Company, Dordrecht, Holland.

Ginsburg H., 1981; The Clinical Interview in Psychological Research on Mathematical Thinking: Aims, Rationales, Techniques. For the Learning of Mathematics, v. 1, 3 pp. 4-11.

Sfard A., 1991; On the dual nature of mathematical conceptions: reflections on processes and objects as differente sides of the same coin, Educational Studies in Mathematics, v. 22, pp. 1-36.

Marovt, Janko, Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia [CT, Thu. 11:00, Room 4]

Homomorphisms of matrix semigroups over division rings from dimension two to three

Let 𝔻 be an arbitrary division ring and M_{n}(𝔻) the multiplicative semigroup of all n × n matrices over 𝔻. We will describe the general form of non-degenerate homomorphisms from M_{2}(𝔻) to M_{3}(𝔻). (with Gregor Dolinar)

Marques, Maria-da-Graça, University of Algarve and CELC, Faro, Portugal [CT, Thu. 16:55, Room 4]

Some conditions for the commutativity of matrix patterns

A matrix pattern P is an array of ∗’s and 0’s. A real matrix A = (a_{i,j}) belongs to pattern P if its dimensions agree with those of P and a_{i,j} ≠ 0 if and only if the i, j entry of P is a ∗. We say that two n-by-n patterns P and Q commute (or allow commutativity) if there exist matrices A ∈ P and B ∈ Q that commute, ie AB = BA. In [1] some necessary and some sufficient conditions are given for the commutativity with the full (all ∗’s) pattern F. In this talk we discuss the necessary conditions in [1] and present some cases where they are sufficient.

[1] C. R. Johnson and M. G. Marques, Patterns of commutativity: the commutant of the full pattern, Electronic Journal of Linear Algebra, 14, 2005. (with C. R. Johnson)

Martínez, José-Javier, Universidad de Alcalá, Alcalá de Henares, Spain [CT, Tue. 18:35, Room 4]

Polynomial regression in the Bernstein basis The problem of polynomial regression in which the usual monomial basis is replaced by the Bernstein basis is considered. The coefficient matrix A of the overdetermined system to be solved in the least-squares sense is then a rectangular Bernstein-Vandermonde matrix. In order to use the method based on the QR decomposition which was developed in the celebrated paper [1], the first stage will consist of computing the bidiagonal decomposition of the coefficient matrix A by means of an extension to the rectangular case of the algorithm presented in [3]. Starting from that bidiagonal decomposition, an algorithm for obtaining the QR decomposition of A due to Koev [2] is then applied. Finally, a triangular system is solved by using the bidiagonal decomposition of the R-factor of A. Some numerical experiments showing the behaviour of our approach are included.

[1] G. Golub: Numerical methods for solving linear least squares problems. Numerische Mathematik 7, 206-216 (1965).

[2] P. Koev: Accurate computations with totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 29(3), 731-751 (2007).

[3] A. Marco, J.-J. Martínez: A fast and accurate algorithm for solving Bernstein-Vandermonde linear systems. Linear Algebra Appl. 422, 616-628 (2007) (with Ana Marco)

Martins, Enide, Centre for Research on Optimization and Control (CEOC), Aveiro, Portugal [CT, Fri. 11:00, Room 3]

On the spectra of some graphs like weighted rooted trees

Let G be a weighted rooted graph of k levels such that, for j ∈ {2, …, k}

1. each vertex at level j is adjacent to one vertex at level j − 1 and all edges joining a vertex at level j with a vertex at level j − 1 have the same weight, where the weight is a positive real number.

2. if two vertices at level j are adjacent then they are adjacent to the same vertex at level j − 1 and all edges joining two vertices at level j have the same weight.

3. two vertices at level j have the same degree.

4. there is not a vertex at level j adjacent to others two vertices at the same level.

In this talk we give a complete characterization of the eigenvalues of the Laplacian matrix of G (analogous characterization can be done for the adjacency matrix of G)). By application of the these results, we derive an upper bound on the largest eigenvalue of a graph defined by a weighted tree and a weigthed triangle attached, by one of its vertices, to a pendant vertex of the tree. (with Rosário Fernandes and Helena Gomes)

Martin, William, North Dakota State University, Fargo, USA [MS4, Tue. 18:10, Room 1]

Integrating learning theories and application-based modules in teaching linear algebra

The research team of The Linear Algebra Project developed and implemented a curriculum and a pedagogy for parallel courses in (a) linear algebra and (b) learning theory as applied to the study of mathematics with an emphasis on linear algebra. The purpose of the ongoing research, partially funded by the National Science Foundation, is to investigate how the parallel study of learning theories and advanced mathematics influences the development of thinking of individuals in both domains. The researchers found that the particular synergy afforded by the parallel study of math and learning theory promoted, in some students, a rich understanding of both domains and that had a mutually reinforcing effect. Furthermore, there is evidence that the deeper insights will contribute to more effective instruction by those who become high school math teachers and, consequently, better learning by their students. The courses developed were appropriate for mathematics majors, pre-service secondary mathematics teachers, and practicing mathematics teachers. The learning seminar focused most heavily on constructivist theories, although it also examined socio-cultural and historical perspectives (von Glaserfeld, 1989; Vygotsky, 1978, 1986). A particular theory, Action-Process-Object-Schema (APOS) (Asiala et al., 1996), was emphasized and examined through the lens of studying linear algebra. APOS has been used in a variety of studies focusing on student understanding of undergraduate mathematics. The linear algebra courses include the standard set of undergraduate topics. This paper reports the results of the learning theory seminar and its effects on students who were simultaneously enrolled in linear algebra and students who had previously completed linear algebra and outlines how prior research has influenced the future direction of the project. (with S. Loch, L. Cooley, M. Meagher, S. Dexter and D. Vidakovic)

McDonald, Judith, Washington State University, Pullman, WA, USA [MS8, Mon. 16:55, Room 1]

Nonnegative and Eventually Nonnegative Matrices

I will discuss the interplay between the properties of nonnegative and eventually nonnegative matrices, and the role that the inverse eigenvalue problem plays in this relationship.

McEneaney, William, University of California, San Diego, La Jolla, United States [MS7, Mon. 11:35, Room 2]

Max-Plus Bases, Cornices and Pruning

In the development of computationally efficient algorithms for control of sensor tasking, one is faced with a certain computational-complexity growth that must be attenuated. At each step of these algorithms, one would like to find a reduced-complexity representation of the current solution. These representations take the form of max-plus sums of affine functionals. Some important max-plus vector spaces, or moduloids, are spaces of convex and semiconvex functions. In these cases, elements of the spaces may be represented as countable max-plus linear combinations of linear (convex-functions spaces) and quadratic (semiconvex-functions spaces) functions. The partial sums naturally approximate the elements from below. In the problem at hand, we are in the case of spaces of convex functions. One solution to the complexity-reduction problem would be simply to begin generating the coefficients in max-plus basis expansions, but one is still left with the problem of which basis functions to choose. More carefully, we see that the problem at hand is as follows: Given an element of the space of convex functions, taking the form of a max-plus sum of M linear functions, and given some fixed, allowable number of approximating affine functions, say N < M, find the best N affine functions to approximate the original element. Of course, there is some freedom in the metric by which we determine what a good approximation is. We choose a metric, say a weighted L_{1} integral, which is convex in a certain sense. One is optimizing this cost functional subject to the constraint the the finite, partial sum, is an approximation from below. The constraint set takes the form of the union of downward pointing cones over the convex hull of coefficients defining the original element, a constraint set termed a cornice here. This particular problem form leads to a solution where the optimal N affine functionals are a subset of the set which defines the original element, that is, pruning is optimal. The problem becomes combinatorial in nature. This structure is not general, and it is not clear which classes of problems may also take this special form.

M. Dopico, Froilán, Universidad Carlos III, Madrid, Spain [Plenary, Tue. 15:30–16:25]

Implicit Jacobi algorithms for the symmetric eigenproblem The Jacobi algorithm for computing the eigenvalues and eigenvectors of a symmetric matrix is one of the

earliest methods in numerical analysis, dating to 1846. It was the standard procedure for solving dense symmetric eigenvalue problems before the QR algorithm was developed. The Jacobi method is much slower than QR or than any other algorithm based on previous reduction to tridiagonal form, and, as a consequence, it is not used in practice. However, in the last twenty years the Jacobi algorithm has received considerable attention because it can compute the eigenvalues and eigenvectors of many types of structured matrices with much more accuracy than other algorithms. The essential idea is to compute first an accurate factorization of the matrix A, and then to apply the Jacobi algorithm implicitly on the factors. The theoretical property that supports this approach is that a factorization A = XDX^{T}, where X is well conditioned and D is diagonal and nonsingular, determines very accurately the eigenvalues and eigenvectors of A, i.e., small componentwise perturbations of D and small normwise perturbations of X produce small relative variations in the eigenvalues of A, and small variations in the eigenvectors with respect the eigenvalue relative gap. The purpose of this talk is to present a unified overview on implicit Jacobi algorithms, on classes of symmetric matrices for which they work, on the perturbation results that are needed to prove the accuracy of the computed eigenvalues and eigenvectors, and, finally, to present very recent developments in this area that include a new, simple, and satisfactory algorithm for symmetric indefinite matrices.

Mead, Jodi, Boise State University, Boise, USA [MS3, Fri. 11:50, Room 2]

Calculating Weights in Least Squares Estimation Using the Chi-squared Method

We will describe the chi-squared method for parameter estimation recently developed by Mead (2007) and Mead and Renaut (submitted). The chi-squared curve method amounts to solving a weighted least squares problem, where the weights are found by ensuring the parameter estimates satisfy the chi-squared test. This method is considerably more efficient, and as accurate as traditional L-curve and cross-correlation methods for parameter estimation. We will show results from Hydrology where data error is calculated by the chi-squared method, and parameter estimates are found within a priori data uncertainty ranges. (with Rosemary Renaut, ASU)

Meerbergen, Karl, K.U. Leuven, Heverlee, Belgium [MS2, Thu. 17:45, Room 1]

Recycling Ritz vectors in the parameterized Lanczos method

The solution of the parameterized system

Ax = f with A = K − ω^{2}M  (16)

with K real symmetric, and M symmetric positive definite arises in applications, including structural engineering and acoustics. The parameter ω is often the frequency and lies in the frequency interval where the numerical model is valid. The solution x is called the frequency response function. The traditional method in engineering is modal superposition where (16) is projected on well selected eigenvectors associated with the eigenvalues of

Ku = λMu .  (17)

This method is usually experienced as very efficient when the eigenvectors and eigenvalues are available, since (16) is transformed to a diagonal linear system, but it requires the computation of a significant amount of eigenvectors. Efficient methods for solving (16) have been developed over the last decade, in the context of iterative linear system solvers for parameterized problems [5] [4], and the Padé via Lanczos method in the context of modelreduction [3] [1] [2]. In this talk, we discuss the use of Ritz vectors to preconditioning the Lanczos method for solving the parameterized system (16). We apply the method for solving (16) with many right-hand sides simultaneously.

[1] Z. Bai and R. Freund. A symmetric band Lanczos process based on coupled recurrences and some applications. Numerical Analysis Manuscript 00-8-04, Bell Laboratories, Murray Hill, New Jersey, 2000.

[2] Z. Bai and R. Freund. A partial Padé-via-Lanczos method for reduced-order modeling. Linear Alg. Appl., 332–334:141–166, 2001.

[3] P. Feldman and R. W. Freund. Efficient linear circuit analysis by Padé approximation via the Lanczos process. IEEE Trans. Computer-Aided Design, CAD-14:639–649, 1995.

[4] K. Meerbergen. The solution of parametrized symmetric linear systems. SIAM J. Matrix Anal. Appl., 24(4):1038–1059, 2003.

[5] V. Simoncini and F. Perotti. On the numerical solution of (λ^{2}A + λB + C)x = b and application to structural dynamics. SIAM Journal on Scientific Computing, 23(6):1876–1898, 2002.

(with Zhaojun Bai)

Meini, Beatrice, Dipartimento di Matematica, Universitá di Pisa, Pisa, Italy [MS6, Tue. 17:20, Room 2]

From algebraic Riccati equations to unilateral quadratic matrix equations: old and new algorithms

The problem of reducing an algebraic Riccati equation XCX − AX − XD + B = 0 to a unilateral quadratic matrix equation (UQME) of the kind P X^{2} + QX + R = 0 is analyzed. New reductions are introduced which enable one to prove some theoretical and computational properties. In particular we show that the structure preserving doubling algorithm of B.D.O. Anderson [Internat. J. Control, 1978] is in fact the cyclic reduction algorithm of Hockney [J. Assoc. Comput. Mach., 1965] and Buzbee, Golub, Nielson [SIAM J. Numer. Anal., 1970], applied to a suitable UQME. A new algorithm obtained by complementing our reductions with the shrink-and-shift technique of Ramaswami is presented. Finally, faster algorithms which require some non-singularity conditions, are designed. The non-singularity restriction is relaxed by introducing a suitable similarity transformation of the Hamiltonian. (with Bini, Dario and Poloni, Federico)

Mena, Hermann, Escuela Politécnica Nacional, Quito, Ecuador [MS6, Tue. 17:45, Room 2]

Exponential Integrators for Solving Large-Scale Differential Riccati Equations

The differential Riccati equation (DRE) arises in several applications, especially in control theory. Partial differential equations (PDEs) constraint optimization problems often lead to formulations as abstract Cauchy problems. Imposing a quadratic cost functional, the resulting optimal control is solved by a feedback control where the feedback operator is given in terms of an operator-valued DRE. Hence, in order to apply such a feedback control strategy to PDE control, we need to solve the large-scale DREs resulting from a spatial semidiscretization. There is a variety of methods to solve DREs. One common approach is based on a linearization that transforms the DRE into a linear Hamiltonian system of first-order matrix differential equations. The analytic solution of this system is given in terms of the exponential of a 2nx2n Hamiltonian matrix. In this talk, we investigate the use of symplectic Krylov subspace methods to approximate the action of this operator and thereby solve the DRE. Numerical examples illustrating the performance of the method will be shown. (with Benner, Peter)

Merlet, Glenn, CNRS/LIAFA, Paris, France [MS7, Tue. 17:45, Room 3]

Semi-group of matrices acting on the max-plus projective space

We investigate the action of a semi-group S of matrices on the max-plus projective space. If all matrices in S are strongly regular (that is, their image has maximal dimension), and the semi-group is primitive (that is one of its elements has only finite entries), then there is a point in the projective space, which is fixed by every matrix in the semi-group. Moreover, S acts on ∩_{M∈S}Im(M), like a finite group of affine isometries. If the semi-group contains an element with projectively bounded image, then it also contains some linear projectors. Then, for any projector P with minimal tropical rank, there is a point x whose orbit is mapped on x by P. Moreover, {P M : M ∈ S} acts on ∩_{M∈S}Im(P M), like a finite group of isometries for the supremum norm. We deduce from this result some limit theorems for max-plus products of random matrices, which were only known under the so-called memory-loss property. These results are useful for performance evaluation of max-plus linear discrete event systems.

Mikkelson, Rana, Iowa State University, Ames, IA, United States of America [CT, Thu. 17:20, Room 3]

Minimum Rank of Graphs with Loops

The minimum rank problem has been studied primarily for undirected simple graphs. We extend cut vertex reduction for finding the minimum rank of an undirected simple graph, which is known to be valid over any field, to undirected graphs with loops, where it is valid over any field that is not ℤ_{2}. We then obtain the result that minimum rank of a tree with loops is field independent except for ℤ_{2}.

Milligan, Thomas, University of Central Oklahoma, Edmond, OK, USA [CT, Fri. 15:55, Room 4]

On Euclidean Squared Distance Matrices

Given n points in Euclidean space, x_{1}, …, x_{n}, a Euclidean Squared Distance (ESD) matrix is a matrix whose entries are of the form (||x_{i} − x_{j}||^{2}). The study of distance matrices is useful in computational chemistry and structural molecular biology. We show some results arising from different characterizations, including facial structure and linear preservers. (with Chi-Kwong Li and Michael Trossett)

Mitchell, Lon, Virginia Commonwealth University, Richmond, United States [CT, Thu. 18:10, Room 3]

Orthogonal Removal of Vertices and Minimum Semidefinite Rank

A vector representation of a graph is an assignment of a vector in ℂ^{n} to each vertex so that nonadjacent vertices are represented by orthogonal vectors and vertices adjacent by a single edge are represented by nonorthogonal vectors. The least n for which a vector representation can be found is the minimum semidefinite rank (msr) of a graph. While the msr of an induced subgraph provides a lower bound for the msr of a graph, a minimal vector representation of a graph need not include a minimal vector representation of a particular subgraph. Orthogonally removing a vertex represented by a vector v⃗ by orthogonally projecting each vector of a vector representation on the orthogonal complement of the span of v⃗ results in a vector representation of a related graph with order decreased by one. We will discuss some of the possibilities and limitations of getting minimal vector representations from orthogonal removal. (with Sivaram Narayan)

Moro, Julio, Universidad Carlos III de Madrid, Leganés, Spain [MS2, Fri. 12:15, Room 1]

Structured Holder condition numbers for eigenvalues under fully nongeneric perturbations

Let λ be an eigenvalue of a matrix or operator A. The condition number κ(A, λ) measures the sensitivity of λ with respect to arbitrary perturbations in A. If A belongs to some relevant class, say 𝕊, of structured operators, one can define the structured condition number κ(A, λ; 𝕊), which measures the sensitivity of λ to perturbations within the set 𝕊. Whenever the structured condition number is much smaller than the unstructured one, the possibility opens for a structure-preserving spectral algorithm to be more accurate than a conventional one. For multiple, possibly defective, eigenvalues the condition number is usually defined as a pair of nonnegative

numbers, with the first component reflecting the worst-case asymptotic order which is to be expected from the perturbations in the eigenvalue. In this talk we adress the case when this asymptotic order differs for structured and for unstructured perturbations: if we denote κ(A, λ) = (n, α) and κ(A, λ; 𝕊) = (n_{𝕊}, α_{𝕊}), we consider the case when n ≠ n_{𝕊}, i.e., when structured perturbations induce a qualitatively different perturbation behavior than unstructured ones. If this happens, we say that the class 𝕊 of perturbations is fully nongeneric for λ. On one hand, we characterize full nongenericity in terms of the eigenvector matrices corresponding to λ,

and it is shown that, for linear structures, this is related to the so-called skew-structure associated with 𝕊. On the other hand, we make use of Newton polygon techniques to obtain explicit formulas for structured condition numbers in the fully nongeneric case: both the asymptotic order and the largest possible leading coefficient are identified in the asymptotic expansion of perturbed eigenvalues for fully nongeneric perturbations. (with María J. Peláez)

Morris, DeAnne, Washington State University, Pullman, USA [MS8, Tue. 11:00, Room 2]

Jordan forms corresponding to nonnegative and eventually nonnegative matrices

We give necessary and sufficient conditions for a set of Jordan blocks to correspond to the peripheral spectrum of a nonnegative matrix. For each eigenvalue, λ, the λ-level characteristic (with respect to the spectral radius) is defined. The necessary and sufficient conditions include a requirement that the λ-level characteristic is majorized by the λ-height characteristic. An algorithm which determines whether or not a multiset of Jordan blocks corresponds to the peripheral spectrum of a nonnegative matrix will be discussed. We also offer necessary and sufficient conditions for a multiset of Jordan blocks to correspond to the spectrum of an eventually nonnegative matrix. (with McDonald, Judith)

Moura, Ana, Instituto Superior Técnico, UTL, Lisbon, Portugal [MS4, Wed. 10:35, Room 2]

Skills, Concepts and Models in a Linear Algebra Course

We present an approach to the organization of a Linear Algebra Course for an engineering degree based on the balance between three pillars: Concepts, Models and Skills. Algorithmic skills is what the students are more familiar with. Concepts is what we mathematicians are used to work in our fundamental research. Models is what drives concepts and needs algorithms to solve, so can be regarded both as a motivator, and as the main objective we want the future engineer to learn in the end. We want them to be able to look at a problem, create a mathematical model for it, conceptualize and analyze the model, and finally to find and interpret the possible solutions.

Instituto Superior Técnico (IST) is the main Engineering school in Portugal. It has around 10000 undergraduate students and 2000 graduate students, in around 21 Majors in Engineering and related topics. The Linear Algebra course is a first semester, first year undergraduate course for all students except Architecture. Students came with a background on one variable calculus and basic geometry. In high school in Portugal, mathematics training emphasis is on algorithmic skills, with no stress on the difference between postulates and deducted results in Mathematics. The students are given “facts" and learn to use them to calculate things. Even this is not well done. With an excessive reliance on calculators, students actually forget simple algebra rules, like distributive property and fraction simplification.

The Linear Algebra traditional approach in IST has until today been focused on teaching concepts, axioms and propositions, with their proofs. On the other hand, students are assessed mainly by exercise resolutions with algorithms (e.g. finding eigenvalues and ei-genvectors, calculating determinants, orthogonalizing basis) with usually only less than 25% of the assessment grade coming from concepts. The result is that the students do not learn the concepts, and thus can only apply the algorithms if they have seen a similar problem solved before, and so know the “recipe".

As pointed out by Schoenfeld (1998), if before the seventies and eighties the main focus was on the knowledge base - facts, procedures and conceptual understanding, now in order to be successful, a mathematics program must include problem solving strategies, metacognition, beliefs, and mathematical practices. In this context, the authors believe that besides the concepts and algorithms, is very important to introduce another pillar, namely models . Mathematics in its history was always inspired by the real world and its properties. Many results in Mathematics were obtained while trying to solve a real world problem, its concepts derived from abstracting regularities found in nature. Models serve as a motivator for both the concepts (the student can see that the concept is useful because it can represent and abstract some existing entity/relation in nature) and the algorithms (we are not just calculating abstract quantities, they are possible solutions to a problem). In short, models create the “intellectual" need for both the concepts and procedures.

Linear Algebra is an ideal field for this exercise, because the invention of the computer increased the importance of Linear Algebra as an engineering tool vis a vis Calculus. Unfortunately, at IST as at other leading Engineering schools around the world, too much importance is still given to Calculus (Strang, 2002).

We, for instance, introduce in our Linear Algebra Course stochastic matrices as simple models for different phenomena, like migrations, voter turnouts, weather prediction, and Leontief production models. For this propose we highly recommend students to read the corresponding sections in books of Linear Algebra with applications by Anton and Rorres (2005) and Lay (2003). The students understand the power of Mathematics, because they can see that one mathematical concept, for instance eigenvalues and eigenvectors of a given stochastic matrix can represent various phenomena, and that learning to solve the abstract problem will allow them to understand and make predictions on all those phenomena. All assessments include at least one phenomenon for the students to model and/or a model for them to analyze, find solutions and interpret.

Interestingly, the students initial reaction tends to be negative. They are used to com-partmentalize knowledge, and are not expecting to have to talk about population growth in a Linear Algebra class. But along the course, they get used to the need of applying concepts and procedures to given models. They get training in analyzing real world problems using Mathematics. They evolve in their ways of understanding and thinking (Harel, 2007) of mathematical solutions as having more than just algebraic meaning, which is one of the most important objectives a mathematics course should give them.

References

Anton, H., and Rorres C. (2005). Elementary Linear Algebra-Applications Version. New York, John Wiley and Sons, Inc. (9th Edition).

Harel G. (In Press). What is Mathematics? A Pedagogical Answer to a Philosophical Question. In R. B. Gold and R. Simons (Eds.), Current Issues in the Philosophy of Mathematics From the Perspective of Mathematicians, Mathematical American Association.

Lay, D. C. (2003). Linear Algebra and its Application. New York, Addison Wesley (3rd Edition).

Schoenfeld A. H. (1998). Toward a Theory of Teaching-in-context. In Issues in Education, Volume 4, N^{o} 1, pp. 1-94.

Strang G. (2002). Too Much Calculus. SIAM Linear Algebra Activity Group Newsletter (2002). (with Santos, P. A.)

Nagy, James, Emory University, Atlanta, USA [Plenary, Wed. 9:10–10:05]

Kronecker Products in Imaging Sciences

Linear algebra and matrix analysis are very important in the imaging sciences. This should not be surprising since digital images are typically represented as arrays of pixel values; that is, as matrices. Due to advances in technology, the development of new imaging devices, and the desire to obtain images with ever higher resolution, linear algebra research in image processing is very active. In this talk we describe how Kronecker and Hadamard products arise naturally in many imaging applications, and how their properties can be exploited when computing solutions of very difficult linear algebra problems.

Nagy, James, Emory University, Atlanta, USA [MS3, Thu. 17:45, Room 2]

Lanczos Hybrid Regularization for Image Processing Applications

Ill-posed problems arise in many image processing applications, including microscopy, medicine and astronomy. Iterative methods are typically recommended for these large scale problems, but they can be difficult to use in practice. For example, it may be difficult to determine an appropriate stopping criteria for fast algorithms, such as the conjugate gradient method; noise contaminates the iterates very quickly, so an imprecise stopping criteria can lead to poor reconstructions. Lanczos based hybrid methods have been proposed to slow the introduction of noise in the iterates. In this talk we discuss the behavior of Lanczos based hybrid methods for large scale problems in image processing. In particular, we discuss how to incorporate regularization and constraints, and how to choose regularization parameters during the iteration process. (with Julianne Chung and Dianne O’Leary)

Narayan, Sivaram, Central Michigan University, Mount Pleasant, Michigan 48859, USA [CT, Fri. 12:15, Room 3]

Linearly Independent Vertices and Minimum Semidefinite Rank

A vector representation of a graph is an assignment of a vector in ℂ^{n} to each vertex so that nonadjacent vertices are represented by orthogonal vectors and vertices adjacent by a single edge are represented by nonorthogonal vectors. The least n for which a vector representation can be found is the minimum semidefinite rank of a graph. We study the minimum semidefinite rank of a graph using vector representations. For example, rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs and certain bipartite graphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank.

Neumann, Michael, Department of Mathematics, University of Connecticut, Storrs, USA [MS8, Tue. 11:50, Room 2]

On Optimal Condition Numbers For Markov Chains

Let T = (t_{i,j}) and T̃ = T − E be arbitrary nonnegative, irreducible, stochastic matrices corresponding to two ergodic Markov chains on n states. A function κ(·) is called a condition number for Markov chains with respect to the (α, β)–norm pair if ∥π − π̃∥_{α} ≤ κ(T)∥E∥_{β}. Various condition numbers, particularly with respect to the (1, ∞) and (∞, ∞) have been suggested in the literature by several authors. They were ranked according to their size by Cho and Meyer in a paper from 2001. In this paper we first of all show that what we call the generalized ergodicity coefficient τ_{p}(∗) = sup_{y^{t}e=0} \frac{∥y^{t}∗∥_{p}}{∥y∥_{1}} , where e is the n–vector of all 1’s, is the smallest of the condition numbers of Markov chains with respect to the (p, ∞)–norm pair. We use this result to identify the smallest condition number of Markov chains among the (∞, ∞) and (1, ∞)–norm pairs. These are, respectively, κ_{3} and κ_{6} in the Cho–Meyer list of 8 condition numbers. Kirkland has studied κ_{3}(T). He has shown that κ_{3}(T) ≥ \frac{n−1}{2n} and he has characterized the properties of transition matrices for which equality holds. We prove again that 2κ_{3}(T) ≤ κ(6) which appears in the Cho– Meyer paper and we characterize the transition matrices T for which κ_{6}(T) = \frac{n−1}{n}. There is only one such matrix: T = (J_{n} − I)/(n − 1). where J_{n} is the n × n matrix of all 1’s. This result demands the development of the cyclic structure of a doubly stochastic matrix with a zero diagonal. Research supported by NSA Grant No. 06G–232 (with Sze, Nung-Sing and Stephen J. Kirkland)

Olesky, Dale, University of Victoria, Victoria, Canada [MS1, Fri. 15:30, Room 1]

Group Inverses of Matrices with Path Graphs

A simple formula for the group inverse of a 2×2 block matrix with a bipartite digraph is given in terms of the block matrices. This formula is used to give a graph-theoretic description of the group inverse of an irreducible tridiagonal matrix of odd order with zero diagonal (which is singular). Relations between the zero/nonzero structures of the group inverse and the Moore-Penrose inverse of such matrices are given. An extension of the graph-theoretic description of the group inverse to singular matrices with tree graphs is conjectured. (with M. Catral and P. van den Driessche)

Olshevsky, Vadim, University of Connecticut, Storrs, USA [CT, Thu. 11:25, Room 4]

Can One Invert a Matrix via Graph Manipulations?

In this paper we use flow graphs to describe the structure for the inverse polynomial Vandermonde matrix (and to design fast O(n^{2}) algorithms that compute it). Although all the results can be derived algebraically, here we reveal a connection to signal processing and deduce new inversion formulas via elementary operations on signal flow graphs for digital filter structures. We introduce, for the first time, several new filter structures (e.g., quasiseparable filters, semiseparable filters, and well-free filters) that generalize the celebrated Markel-Gray structure, widely used in speech processing. No knowledge of system theory (or anything beyond matrices) is required, we will start with an elementary 5-minutes tutorial on flow graphs, and show how their use dramatically simplifies the derivation of inversion formulas. (with Tom Bella and Pavel Zhlobich)

Olshevsky, Vadim, University of Connecticut, Storrs, USA [MS2, Fri. 10:35, Room 1]

Lipschitz stability of canonical Jordan bases of H-selfadjoint matrices

We study Jordan-structure-preserving perturbations of matrices selfadjoint in the indefinite inner product. The main result is Lipschitz stability of the corresponding so-called similitude matrices. The result can be reformulated as Lipschitz stability, under small perturbations, of canonical Jordan bases (i.e., eigenvectors and generalized eigenvectors enjoying a certain flipped orthonormality relation) of matrices selfadjoint in the indefinite inner product. The proof relies upon the analysis of small perturbations of invariant subspaces, where the size of a permutation of an invariant subspace is measured using the concepts of a gap and of a semigap. (with Tom Bella and Upendra Prasad)

Palma, Alejandro, Instituto de Física (BUAP), Puebla, México [CT, Thu. 11:50, Room 4]

Solution of the linear time-dependent potential by using a solvable Lie algebra^{∗}

The solution of the Schödinger equation for the linear time-dependent potential has been recently the subject matter of several publications. We show in this work that this is one of the few systems which leads to a solvable Lie algebra. In fact, we consider a more general potential where the linear time-dependent potential is only a particular case. We find the solution by using the well known theorem of Wei-Norman. (with M. Villa, and L. Sandoval)

Parraguez, Marcela, Pontificia Universidad Católica de Valparaíso, Valparaíso, Chile [MS4, Mon. 12:00, Room 1]

Construction of a vector space schema

From a cognitive point of view the vector space concept is one that causes many difficulties for students of Linear Algebra. Apart from being abstract in itself, it has to be connected with several other abstract concepts in the mind of a student in order to claim that understanding takes place. In this research project our aim is to explain the construction of the vector space concept from the viewpoint of APOS (Action — Process — Object — Schema) theory. We are also interested in studying the formation and evolution of the vector space schema and how other concepts such as linear independence and basis are incorporated into the students’ mathematical world in connection with this schema. The methodological framework of APOS theory requires that the concept in question be analyzed theoretically resulting in a viable map (called a genetic decomposition) of student learning in terms of mental constructions. In our talk we will present a possible genetic decomposition for the construction of the vector space concept and provide empirical evidence for specific mental constructions that students make when they are learning this concept. This evidence was gathered through questionnaires and interviews (designed in line with our genetic decomposition) applied to undergraduate students who were taking a Linear Algebra course. These instruments also help in identifying student difficulties with the vector space concept and some related concepts such as binary operations, axioms and fields. (with Oktaç, Asuman)

Patricio, Pedro, Departamento de Matemática, Universidade do Minho, Braga, Portugal [CT, Fri. 11:50, Room 4]

Some additive results on Drazin Inverses

Our aim is to investigate the existence of the Drazin inverse (p + q)^{d} of the sum p + q, where p and q are either ring elements or matrices, and a^{d} denotes de Drazin inverse of a. We recall that the Drazin inverse a^{d} of a is the unique solution, if it exists, to a^{k}xa = a^{k}, xax = x, ax = xa, for some integer k ≥ 0. In this talk, we will give sufficient conditions in order to p + q be Drazin invertible, generalizing recent results, and give converse results assuming the ring is Dedekind-finite. (with R. E. Hartwig)

Peña, Juan Manuel, University of Zaragoza, Zaragoza, Spain [Plenary, Wed. 8:10–9:05]

From Total Positivity to Positivity: related classes of matrices

Matrices with all their minors nonnegative (respectively, positive) are usually called totally nonnegative

(respectively, totally positive). These matrices present nice stability properties as well as interesting spectral, factorization and variation diminishing properties. They play an important role in many applications to other fields such as Approximation Theory, Mechanichs, Economy, Optimization, Combinatorics or Computer Aided Geometric Design. We revisit some of the properties and applications of these matrices and show some recent advances. Moreover, we show that some results and techniques coming from Total Positivity theory have been extended to other classes of matrices which are also closely related to positivity. Among these other clases of matrices we consider sign regular matrices (which generalize totally nonnegative matrices), some classes of P-matrices (matrices whose principal minors are positive), including M-matrices, and conditionally positive definite (and conditionally negative definite) matrices.

Peña, Marta, Universitat Politecnica de Catalunya, Barcelona, Spain [CT, Tue. 11:00, Room 4]

Perturbations preserving conditioned invariant subspaces

Invariant subspaces play a key role both in square matrices and linear systems, where they are often called “conditioned" invariant subspaces. In the context of versal deformations, invariant subspaces arise in a natural way. For instance, in the Carlson problem (that is, the possible Segre characteristic of a block-triangular nilpotent matrix when diagonal blocks are prescribed), one asks for perturbations of the given matrix preserving a prefixed invariant subspace. The “interesting class" of the so-called marked subspaces, namely, the invariant subspaces having a Jordan basis which can be extended to a Jordan basis of the whole space is also considered in this work. For instance, it is known that the “simplest" solutions of the Carlson problem are marked, and any other appears in a neighborhood of the marked ones. This notion can be extended to pairs of matrices and used for the analogue to the Carlson problem: again the marked Solutions cover all the possibilities and are the simplest realizations. Here we tackle the perturbation of a linear system preserving a given conditioned invariant subspace. We focus our attention on the marked case which, as above, has interesting properties; for instance the “minimal" observable perturbations of a non-observable pair are marked. We obtain the equations of a miniversal deformation of a pair of matrices preserving a given conditioned invariant subspace and solve them explicitly, obtaining “minimal" solutions (that is, without repeated parameters). Some applications are derived: computation of the dimension of the orbits, characterization of structurally stable objects, study of bifurcations diagrams... (with A. Compta and J. Ferrer)

Perdigão, Cecília, Faculdade de Ciências e Tecnologia-UNL, Lisboa, Portugal [CT, Thu. 17:45, Room 3]

On the equivalence class graph

For a given simple, connected and undirected graph G = (V (G), E(G)) we define an equivalence relation R on V (G) such that

∀_{x,y∈V (G)} xRy ⇔ N(x) = N(y),

where, for all x in V (G), N(x) is the set of all neighbors of x. The equivalence class graph of G, or R-graph of G, is the graph G = (V (G), E(G)) where V (G) = {X_{1}, …, X_{p}} is the set of equivalence classes of R in V (G) and {X_{i}, X_{j}} ∈ E(G) if, and only if, there exists x ∈ X_{i} and y ∈ X_{j} such that {x, y} is an edge in G. In our last work we have computed the minimum rank of G using the R- graph of G. Although in various cases this computation was simplified, there exist graphs whose R-graph is equal to the graph itself and for whose we do not have any simplification by this construction. Our aim is study the properties of the equivalence class graph and, more particulary, characterize simple connected and undirected graphs which are equal to its equivalence class graph. (with Rosário Fernandes)

Plavka, Jan, Technical University, Kocice, Slovakia [MS7, Wed. 11:50, Room 3]

On the robustness of matrices in max-min algebra

Let (B, ≤) be a nonempty, bounded, linearly order set and a ⊕ b = max(a, b), a ⊗ b = min(a, b) for a, b ∈ B. A vector x is said to be an eigenvector of a square matrix A if A ⊗ x = λ ⊗ x. A given matrix A is called (strongly) robust if for every x the vector A^{k} ⊗ x is an (greatest) eigenvector of A for some natural number k. We present a characterization of robust and strongly robust matrices. As a consequence, an efficient algorithm for checking of it is introduced.

References

[1] P. Butkovič and R. A. Cuninghame-Green, On matrix powers in max-algebra, Lin. Algebra and its Appl. 421 (2007) 370-381.

[2] K. Cechlárová, Eigenvectors in bottleneck algebra, Lin. Algebra Appl. 175 (1992), 63- 73.

[3] J. Plavka, On the robustness of matrices in max-min algebra (submitted to LAA).

Plestenjak, Bor, University of Ljubljana, Ljubljana, Slovenia [MS2, Thu. 18:10, Room 1]

Numerical methods for two-parameter eigenvalue problems

We consider the two-parameter eigenvalue problem [1]

A_{1}x_{1} = λB_{1}x_{1} + μC_{1}x_{1}, (18) A_{2}x_{2} = λB_{2}x_{2} + μC_{2}x_{2},

where A_{i}, B_{i}, and C_{i} are given n_{i} × n_{i} matrices over ℂ, λ, μ ∈ ℂ, and x_{i} ∈ ℂ^{n_{i}} for i = 1, 2. A pair (λ, μ) is an eigenvalue if it satisfies (18) for nonzero vectors x_{1}, x_{2}. The tensor product x_{1} ⊗ x_{2} is then the corresponding eigenvector. On the tensor product space S := ℂ^{n_{1}} ⊗ ℂ^{n_{2}} of the dimension N := n_{1}n_{2} we can define operator determinants

Δ_{0} = B_{1} ⊗ C_{2} − C_{1} ⊗ B_{2},
Δ_{1} = A_{1} ⊗ C_{2} − C_{1} ⊗ A_{2},
Δ_{2} = B_{1} ⊗ A_{2} − A_{1} ⊗ B_{2}.

The two-parameter problem (18) is nonsingular if its operator determinant Δ_{0} is invertible. In this case Δ_{0}^{−1}Δ_{1} and Δ_{0}^{−1}Δ_{2} commute and problem (18) is equivalent to the associated problem

Δ_{1}z = λΔ_{0}z, (19) Δ_{2}z = μΔ_{0}z

for decomposable tensors z ∈ S, z = x_{1}⊗x_{2}. Some numerical methods and a basic theory of the two-parameter eigenvalue problems will be presented. A possible approach is to solve the associated couple of generalized eigenproblems (19), but this is only feasible for problems of low dimension because the size of the matrices of (19) is N × N. For larger problems, if we are interested in a part of the eigenvalues close to a given target, the Jacobi–Davidson method [3, 4, 5] gives very good results. Several applications lead to singular two-parameter eigenvalue problems where Δ_{0} is singular. Two such examples are model updating [2] and the quadratic two-parameter eigenvalue problem

(S_{00} + λS_{10} + μS_{01} + λ^{2}S_{20} + λμS_{11} + μ^{2}S_{02})x = 0 (20) (T_{00} + λT_{10} + μT_{01} + λ^{2}T_{20} + λμT_{11} + μ^{2}T_{02})y = 0.

We can linearize (20) as a singular two-parameter eigenvalue problem, a possible linearization is

([\begin{matrix}S_{00} & S_{10} & S_{01} \\ 0 & −I & 0 \\ 0 & 0 & −I \end{matrix}] + λ [\begin{matrix}0 & S_{20} & \frac{1}{2}S_{11} \\ I & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] + μ [\begin{matrix}0 & \frac{1}{2}S_{11} & S_{02} \\ 0 & 0 & 0 \\ I & 0 & 0 \end{matrix}]) x̃ = 0

([\begin{matrix}T_{00} & T_{10} & T_{01} \\ 0 & −I & 0 \\ 0 & 0 & −I \end{matrix}] + λ [\begin{matrix}0 & T_{20} & \frac{1}{2}T_{11} \\ I & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] + μ [\begin{matrix}0 & \frac{1}{2}T_{11} & T_{02} \\ 0 & 0 & 0 \\ I & 0 & 0 \end{matrix}]) ỹ = 0,

where x̃ = [\begin{matrix}x \\ λx \\ μx \end{matrix}] and ỹ = [\begin{matrix}y \\ λy \\ μy \end{matrix}]. Some theoretical results and numerical methods for singular two-

parameter eigenvalue problems will be presented.

References

[1] F. V. Atkinson, Multiparameter eigenvalue problems, Academic Press, New York, 1972.

[2] N. Cottin, Dynamic model updating — a multiparameter eigenvalue problem, Mech. Syst. Signal Pr., 15 (2001), pp. 649–665.

[3] M. E. Hochstenbach and B. Plestenjak, A Jacobi–Davidson type method for a right definite twoparameter eigenvalue problem, SIAM J. Matrix Anal. Appl., 24 (2002), pp. 392–410.

[4] M. E. Hochstenbach, T. Košir, and B. Plestenjak, A Jacobi–Davidson type method for the nonsingular two-parameter eigenvalue problem, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 477–497.

[5] M. E. Hochstenbach and B. Plestenjak, Harmonic Rayleigh–Ritz extraction for the multiparameter eigenvalue problem, to appear in ETNA.

Ponce, Daniela, University of Hradec Králové, Hradec Králové, Czech Republic [MS7, Mon. 12:25, Room 2]

NP-hard problems in extremal algebras tackled by particle swarm optimization

The aim of the contribution is to present an application of a non-standard method called particle swarm optimization (PSO), in the area of extremal algebras. Many of the problems studied in max-plus or max-min algebra cannot be solved in polynomial time and have been shown to be NP-hard. From the practical point of view, finding an approximate or suboptimal solution can be a considerable achievement in comparison with the situation when no solution is available. New ways of computation are being developed for attacking these directly intractable problems. Permuted eigenvector problem (PEV) has been recently investigated in max-plus algebra: Given a square matrix A and a vector x of the same dimension, is there a permutation π such that the permuted vector x_{π} is an eigenvector of A? It has been proved that PEV and several other related problems are NP-complete, see [2]. On the other side, analogous problems are polynomially solvable in max-min algebra, see [4], [5]. In the contribution, PEV in both versions, max-plus and max-min, has been solved by the particle swarm optimization method, the results have been analysed and convergence conditions described. PEV can be approached as an optimization problem. When square matrix A and vector x of dimension n are given, then vector variable y is considered, with the constraint that y is a permutation of x. An objective function z = ∥A ⊗ y − y∥ should be set to minimum. The answer in the given instance of PEV is ‘yes’ exactly when the minimal value of z is zero. The operation ⊗ in the definition of the objective function z denotes the matrix multiplication in the corresponding extremal algebra (max-plus, or max-min). Particle swarm optimization (PSO) is a global stochastic optimization technique developed by Kennedy and Eberhart [6]. PSO is population-based optimization algorithm imitating social behavior. The optimization algorithm starts by a creation of a population (swarm) of randomly constructed candidate solutions (particles) resulting in initial location of particles in the solution space. Position of the swarm in the solution space is then repeatedly adjusted based on consideration of previous best positions of each individual particle in the solution space as well as best positions attained by neighbouring particles (various neighbourhood topologies can be defined). The basic variant of PSO algorithm was proved to be not a local optimizer. However, such variants of PSO algorithm exist which were proved to be global optimization algorithms [1]. Examples of successful applications of PSO are related to design problems [3], scheduling and planning problems [9] or applied mathematics problems [7], [8], [10]. In tackling PEV as optimization problem we deal with a discrete variant of PSO. Each particle y is a random permutation of x and the swarm is a set of permutations. The solution space is composed of all permutations of x. Objective function of a particle is z as defined above, i.e. the norm of the difference A⊗y−y. The computational ability of PSO to find a solution of PEV has been experimentally tested.

References

[1] F. van den Bergh, An Analysis of Particle Swarm Optimizers, PhD thesis, Department of Computer Science, University of Pretoria, Pretoria, South Africa (2002).

[2] P. Butkovič: Permuted max-algebraic (tropical) eigenvector problem is NP-complete, Linear Algebra and its Applications 428 (2008), 1874-1882.

[3] C.A. Coello Coello, E.H.N. Luna, A.H.N. Aguirre, Use of Particle Swarm Optimization to Design Combinational Logic Circuits, Lecture Notes in Computer Science, Springer-Verlag, 2606 (2003), 398-409.

[4] M. Gavalec, J. Plavka, Simple image set of linear mappings in a max-min algebra, Discrete Applied Mathematics 155 (2007), 611-622.

[5] M. Gavalec, J. Plavka, Permuted max-min eigenvector problem (to appear in Proc. of the ILAS Conference 2008, Cancún).

[6] J. Kennedy, R.C. Eberhart, Particle Swarm Optimization, Proc. of the IEEE International Conference on Neural Networks, Piscataway, NJ, USA (1995), 1942-1948.

[7] E.C. Laskari, K.E. Parsopoulos, M.N. Vrahatis, Particle Swarm Optimization for Minimax Problems, Proc. of the IEEE Congress on Evolutionary Computation, 2 (May 2002), 1576-1581.

[8] E.C. Laskari, K.E. Parsopoulos, M.N. Vrahatis, Particle Swarm Optimization for Integer Programming, Proc. of the IEEE Congress on Evolutionary Computation, 2 (May 2002), 1582-1587.

[9] A. Salman, I. Ahmad, S. Al-Madani, Particle Swarm Optimization for Task Assignment Problem, Microprocessors and Microsystems, 26(8) (2002), 363-371.

[10] Y. Shi, R.A. Krohlin, Co-evolutionary Particle Swarm Optimization to Solve min-max Problems, Proc. of the IEEE Congress on Evolutionary Computation, 2 (May 2002), 1682-1687. (with Gavalec, Martin)

Poole, George, East Tennessee State University, Johnson City, USA [CT, Mon. 17:20, Room 2]

Whatever Happened to Rook’s Pivoting?

In 1991, Poole and Neal (LAA 149:249-272) presented a geometric analysis of both phases of Gaussian Elimination (GE) in order to better understand how partial pivoting, total pivoting, scaling, and condition number influence the computed solution of a system of linear equations in a finite-precision (F-P)environment. What emerged from this geometric analysis was a new pivoting strategy, Rook’s Pivoting, that addressed all of the issues normally associated with GE in a F-P environment: pivoting, scaling, and condition number. The work was presented through a series of papers. Here we review the implication of these papers in both LA education, and LA application. The talk should be both illuminating and entertaining.

Possani, Edgar, ITAM- Instituto Tecnológico Autónomo de México, México, México [MS4, Wed. 11:25, Room 2]

Use of models in the teaching of linear algebra

In this talk we will present an approach to teaching linear algebra using models. In particular, we are interested in analyzing the models and modeling (Lesh 2003) approach under an APOS perspective. We will present a short illustration of the analysis on a problem related to traffic flow that elicits the use of a system of linear equations and different parameterizations of this system to answer questions on traffic control. Carlson et. al. (1997) have done some research regarding the main obstacles faced by students when approaching notions and tools of linear algebra. Their work suggests the use of problems that go beyond simple exercises, especially those that come from other subject areas, which can enrich and motivate a significant learning experience. Under Lesh’s models and modeling approach a candidate problem should follow six principles in order to qualify for such analysis as a model-eliciting activity. We have employed these criteria when selecting and analyzing problems that could later be used in the teaching of linear algebra. We complement this analysis by following an APOS approach. The Action-Process-Object-Schema (APOS) theory was built on Piaget’s work and constructivist ideas (Dubinsky, 1992, 1994). It intends to model the way students learn advanced mathematical topics by analyzing the mathematical concepts involved in a certain problem. Through the genetic decomposition of concepts it is possible to define specific actions, processes and objects that students conceptualize as they learn. This description enables researchers to have a clearer idea of the learning processes and to design appropriate questions for students to tackle. Our aim is to analyze modeling problems through the careful design of activities that promote significant development of mathematical reasoning in a meaningful situation or realistic setting. We will present an analysis of the problem with the help of APOS theory and the design of activities that can help students develop their learning. We propose trying out these activities together with the problem in order to analyze its effectiveness in describing the learning process. The traffic flow problem asks of students several specific questions on traffic control on a grid of streets in a busy financial district of a city. It has already been used in the classroom by one of the researchers who is also a linear algebra teacher. It is our experience that students encounter great difficulties in identifying the variables and the problem conditions that might enable them in setting the linear equations necessary to describe a system of simultaneous equations to model the problem. Our chosen problem allows this to become evident, and to identify where the difficulties lie. In the process of exploring different parameterizations, students find graphical representations for the region of possible parameter values (plausible values for the traffic flow). These different parameterizations help them identify an adequate one with which to answer specific questions on traffic control. The realistic setting of the problem motivates this analysis by the students. This will work will be presented in a full version as a paper at the conference. (with Preciado, G. and Lozano, D.)

Prokip, Volodymyr, Institute of Appl. Problem for Mech. and Math. NAS of Ukr, L’viv, Ukraine [CT, Thu. 16:55, Room 5]

On the problem of diagonalizability of matrices over a principal ideal domain

Let R – be a principal ideal domain with the unit element e ≠ 0 and U(R) the set of divisors of unit element e. Further, let R_{n} – the ring of (n × n)-matrices over R; I_{k} – the identity k × k matrix and O the zero n × n matrix. In this report we present conditions of diagonalizability of a matrix A ∈ R_{n}, i.e. when for A there exists a matrix T ∈ GL(n, R) such that T AT^{−1} – a diagonal matrix. Theorem. Let A ∈ R_{n} and

det(Ix − A) = (x − α_{1})^{k_{1}}(x − α_{2})^{k_{2}} ⋯ (x − α_{r})^{k_{r}},

where α_{i} ∈ R, and α_{i} − α_{j} ∈ U(R) for all i ≠ j. If m(x) = (x − α_{1})(x − α_{2}) ⋯ (x − α_{r}) – the minimal polynomial of the matrix A, i.e. m(A) = O, then for the matrix A there exists a matrix T ∈ GL(n, R) such that

T AT^{−1} = diag (α_{1}I_{k_{1}}, α_{2}I_{k_{2}}, …, α_{r}I_{k_{r}}) .

Protasov, Vladimir, Moscow State University, Moscow, Russia [CT, Wed. 11:50, Room 4]

p-radii of linear operators and equations of self-similarity

p-radii of linear operators extend the notion of the joint spectral radius, they are known since 1995. We prove that for any p ∈ [1, +∞] a finite irreducible family of linear operators possesses an extremal norm corresponding to its p-radius. As a corollary we derive a criterion for the L_{p}-contractibility property of linear operators and estimate the asymptotic growth of orbits for any point. These results are applied in analysis of functional difference equations with linear contractions of the argument (self-similarity equations). Spacial cases of such equations are well-known: fractal curves (de Rhum, Koch curves, etc.), refinement equations and so on. We obtain a sharp criterion for the existence and uniqueness of solutions of the self-similarity equations in various functional spaces, compute the exponents of regularity and estimate moduli of continuity. This, in particular, gives a geometric interpretation of the p-radius in terms of spectral radii of certain operators in the space L_{p}[0, 1].

Pruneda, Rosa E., University of Castilla-La Mancha, Ciudad Real, Spain [CT, Tue. 11:00, Room 3]

Complete Orthogonal Decomposition Compared with Direct Projection Methods

Several variants of projection methods have been applied to solve linear systems of equations and matrix computations. These methods are direct solvers and consist of an iterative process that projects the orthogonal subspace of each row of a matrix in the orthogonal subspace of the previous ones. The pivoting process is based on the dot products of the rows of the matrix and a base of the Euclidean space, which is transformed at each iteration considering orthogonal relationships. This paper studies the orthogonal decomposition method that gives a complete decomposition of the Euclidean space. The method is compared with the direct projection method, which is based on the same pivoting strategy, but gives an implicit factorization of the matrix. The execution and the numerical cost of detecting linear dependencies, solving multiple linear systems and updating one-rank modification problems are discussed. An application to linear regression problems illustrates how to detect collinear relations and to obtain the coefficients of such dependencies with both methods. (with Beatriz Lacruz)

Pryporova, Olga, Iowa State University, Ames, IA, USA [MS1, Wed. 11:50, Room 1]

Potential Diagonal and D-convergence

It is well known that a matrix A is convergent (i.e. its spectral radius is less than 1) if and only if the Stein linear matrix inequality X − A^{∗}XA ≻ 0 has a positive definite solution X = P. A stronger type of convergence, useful in many applications, is diagonal convergence, where a positive diagonal solution P exists. Diagonal convergence guarantees, in particular, that a matrix will remain convergent under multiplicative diagonal perturbations D with |D| ≤ I. A matrix A such that DA is convergent for all diagonal matrices D, where |D| ≤ I, is called D-convergent. In my talk I will present some results on the relations between diagonal, D-convergence, and introduce connections to qualitative convergence.

Renaut, Rosemary A., Department of Mathematics and Statistics, Tempe, USA [MS3, Thu. 18:35, Room 2]

A Newton Iteration for estimating the regularizing parameter for least squares

Recently, Mead showed that a statistical result on the χ^{2}-distribution of the Tikhonov cost functional for least squares problems can be used for estimating an optimal regularizing parameter. Here we explain the background and development of a Newton iteration from which the regularizing parameter can be efficiently and effectively found. We contrast the Newton iteration with and without solution using the Generalized Singular Value Decomposition, hence demonstrating that one can efficiently find solutions without the GSVD. At each Newton step a solution of the regularized problem needs to be found for the current value of the regularization parameter. We also investigate the sensitivity of the solution to the accuracy of calculating these intermediate steps of the Newton iteration, hence demonstrating that the overall ideal regularization parameter can be obtained without significant overhead as compared to one solution of the given problem. (with Jodi Mead, Boise State University)

Roca, Alicia, Dpto. de Matemática Aplicada, Universidad Politécnica, Valencia, Spain [CT, Tue. 11:25, Room 4]

Pencils with Prescribed Constant Subpencils

We present a result within the scope of the matrix pencil completion problem. We characterize the existence of an arbitrary pencil with a prescribed constant subpencil, in terms of very simplified conditions and for algebraically closed fields. (with F. C. Silva)

Rodríguez, Juan Alberto, Universitat Rovira i Virgili, Tarragona, España [CT, Fri. 11:50, Room 3]

The Laplacian Spectrum of Hypergraphs

In order to deduce properties of graphs from results and methods of algebra, firstly we need to translate properties of graphs into algebraic properties. In this sense, a natural way is to consider algebraic structures or algebraic objects as, for instance, groups or matrices. In particular, the use of matrices allows us to use methods of linear algebra to derive properties of graphs. There are various matrices that are naturally associated with graphs, such as the adjacency matrix, the Laplacian matrix, and the incidence matrix. One of the main aims of algebraic graph theory is to determine how, or whether, properties of graphs are reflected in the algebraic properties of such matrices. In this paper we collect some resent results on the Laplacian spectrum of hypergraphs. We focuss our attention on metric parameters, including eccentricity, excess, diameter and Wiener index. Throughout this paper we particularize the results to the case of walk-regular hypergraphs. (with Aida Kamisalic)

Rosenthal, Peter, University of Toronto, Canada [Plenary, Fri. 8:10–9:05]

Invariant subspaces of semigroups of matrices

By a “semigroup of matrices" we simply mean a collection of square complex matrices that is closed under multiplication. This will be a completely self-contained survey of some results related to invariant subspaces of such semigroups. It will begin with a maximally-simple proof of Burnside’s Theorem (obtained in joint work with Halperin and Lomonosov) that has the immediate corollary that a semigroup is irreducible (i.e., has only the trivial invariant subspaces) if and only if its linear span is the space of all matrices. A proof will be presented of a joint result with Heydar Radjavi that an irreducible semigroup is finite, countable or bounded if the range of a non-zero linear functional restricted to the semigroup has the corresponding property. Another joint result with Radjavi gives a sufficient condition that an irreducible semigroup be similar to a semigroup consisting of multiples of unitary matrices. In a sense, the opposite of “irreducible" is “triangularizable." To the extent that time permits, there will be discussion of sufficient conditions (due to many mathematicians) that a semigroup be similar to a semigroup of upper triangular matrices.

Rump, Siegfried M., Hamburg University of Technology, Hamburg, Germany [CT, Mon. 17:45, Room 3]

The ratio between the Toeplitz and the unstructured condition number

Recently we showed that the ratio between the normwise Toeplitz structured condition number of a linear system and the general unstructured condition number has a finite lower bound. However, the bound was not explicit, and nothing was known about the quality of the bound. In a joint work with H. Sekigawa we give an explicit lower bound only depending on the dimension, and we show that this bound is almost sharp. The solution of both problems is based on the minimization of the smallest singular value of a class of Toeplitz matrices and its nice connection to a lower bound on the coefficients of the product of two polynomials. (with H. Sekigawa)

Russo, Maria Rosaria, Department of Mathematics - University of Padua, Padova, Italy [CT, Tue. 16:55, Room 4]

On some general determinantal identities of Sylvester type

Sylvester’s determinantal identity is a well-known identity in matrix analysis which expresses a determinant composed of bordering determinants in terms of the original one. It has been extensively studied, both in the algebraic and in the combinatorial context and is frequently used in context as approximation, linear programming and extrapolation algorithms. Several authors have deepened the main property of this classical Sylvester’s identity, some of these have obtained significant results as generalized formulas. In this talk we present a new generalization of the Sylvester’s determinantal identity, which expresses the determinant of a matrix in relation with the determinant of the bordered matrices obtained adding more than one row and one column to the original matrix. (with Michela Redivo-Zaglia)

Rust, Bert W., National Institute of Standards and Technology, Gaithersburg, MD, USA [MS3, Thu. 16:55, Room 2]

A Truncated Singular Component Method for Ill-Posed Problems

The truncated singular value decomposition (TSVD) method for solving ill-posed problems regularizes the solution by neglecting contributions in the directions defined by singular vectors corresponding to small singular values. In this work we propose an alternate method, neglecting contributions in directions where the measurement value is below the noise level. We call this the truncated singular component method (TSCM). We present results of this method on test problems, comparing it with the TSVD method and with Tikhonov regularization. (with Dianne P. O’Leary, University of Maryland)

Salam, Ahmed, Université du Littoral-Côte d’Opale, Calais, France [CT, Tue. 18:10, Room 4]

A structure-preserving Arnoldi-like method for a class of structured matrices

The aim of this talk is to introduce an Arnoldi-like method that preserves the structures of a large set of structured matrices. Interesting particular elements of such set are Hamiltonian, skew-Hamiltonian and symplectic matrices. The obtained structure-preserving size reduction is crucial for the computation of several eigenvalues of such large and sparse structured matrices.

Sánchez Perales, Salvador, Benemérita Universidad Autónoma de Puebla, Puebla, México [CT, Thu. 11:00, Room 3]

Manifold of proper elements

Let X be a Banach space and let B(X) denote the space of all bounded linear transformation on X. With

Eig(X) = {(λ, L, A) ∈ C × P_{1}(X) × B(X) : A(L) ⊂ L and A_{|L} = λI}

we denote the manifold of proper elements of X and let (λ_{0}, L_{0}, A_{0}) ∈ Eig(X) be a fix arbitrary element. In the first part of this note we give necessary and sufficient conditions that (λ, L, A) ∈ Eig(X) using the system of equations determinate with (λ_{0}, L_{0}, A_{0}) ∈ Eig(X). In the second part we apply this result to describe relation between multiplicity of eigenvalue λ_{0} of the operator A_{0} and the spectrum of the operator Â_{0} from quotient X/L_{0} to itself definite with Â_{0}(x + L_{0}) = A_{0}(x) + L_{0}. (with S. Djordjevic)

Satô, Kenzi, Tamagawa University, Tokyo, Japan [CT, Thu. 12:15, Room 4]

The algebraic relations of curvatures of PL manifolds

There are two types of the Gauss-Bonnet theorems for PL manifolds, Banchoff’s theorem (the sum of Banchoff’s curvature of all vertices is equal to the Euler number) and Homma’s theorem (the alternative sum of Homma’s curvature of all faces is equal to the Euler number). In this talk, the algebraic relations of these curvatures are considered.

Schaeffer, Elisa, Universidad Autónoma de Nuevo León, San Nicolás de los Garza, México [CT, Fri. 11:25, Room 3]

Locally computable approximations of absorption times for graph clustering

Graph clustering aims to partition a given graph into groups of tightly interrelated vertices. In local clustering, the aim is to identify the group in which a given seed vertex belongs. We study the problem of local clustering based on the mathematics of random walks in graphs. In this work, we first algebraically express the absorption times of a random walk to the seed vertex in terms of the spectrum of a matrix representation of the graph’s adjacency relation. We argue and experimentally demonstrate that a single eigenvector often suffices to obtain a good approximate for the absorption times from all other vertices to the seed. We then use a locally computable gradient-descent method to approximate this eigenvector based on its formulation in terms of an optimization problem of the Rayleigh quotient. In order to carry out the local clustering, we interpret the components of the resulting approximation vector as vertex similarities and compute the cluster of the seed vertex as a standard two-classification task on the components of the vector. At no phase of the proposed method for local clustering is it necessary to resort to global information of the graph. This method ties together a well-established field of spectral clustering and the absorption times of a random walk, hence permitting extensions to clustering directed graphs in terms of local approximations to absorption times, whereas much of the matrix algebra used in spectral clustering of undirected graphs is not directly applicable to the asymmetric matrices that rise from directed graphs. (with Pekka Orponen and Vanesa Avalos)

Schaffrin, Burkhard, Ohio State University, Columbus, OH, USA [CT, Wed. 11:00, Room 4]

Total least-squares regularization of Tykhonov type and an ancient racetrack in Corinth

In this contribution a variation of Golub/Hansen/O’Leary’s Total Least-Squares (TLS) regularization technique is introduced, based on the Hybrid APproximation Solution (HAPS) within an Errors-in-Variables (EIV) model. After developing the (nonlinear) estimator through a traditional Lagrange approach, the new method is applied to a problem from archeology. There, both the radius and the center of a circle have to be found, of which only a small part of the arc had been surveyed in-situ, thereby giving rise to an ill-conditioned set of equations. According to the archeologists involved, this circular arc served as the starting line of a racetrack in the ancient Greek stadium of Corinth, ca.500 BC. The present study compares previous estimates of the circle parameters with the newly developed “Regularized TLS Solution of Tykhonov type". (with Kyle Snow)

Schneider, Hans, University of Wisconsin, Madison, Madison, WI, USA [MS7, Wed. 12:15, Room 3]

Nonnegative linear algebra and max linear algebra: where’s the difference?

There are substantial similarities in corresponding results in the two forms of linear algebra mentioned in the title, and there are differences. We briefly explore the reason for the differences and some consequences.

Sebeldin, Anatoly, University UGANC, Guinea, Conakry, Guinea [CT, Thu. 11:50, Room 5]

Algorithm resolving problem of determination of finite cyclicgroup by its automorphism group

We say, that group G is determined by its automorphism group in some class X if Aut(G) ≅ Aut(H) imply H ≅ G for any H ∈ X. For any finite cyclic group the matrix of its automorphism group and the algorithm of comparison of these matrices are obtained. Thus, the problem of determination of finite cyclicgroup Z(n) is reduced to search a number m ≠ n such, that A(n) = A(m) where A(n) and A(m) are the matrices of Aut(Z(n)) and Aut(Z(m)).

Literature:[1] Dètermination d’un groupe cyclique par son groupe des automorphismes A. Sebeldin, A. Sylla, Revue des sciences. UGANC, 4 (2002), 26-30. (with V. K. Vildanov and A. L. Sylla)

Seddighin, Morteza, Indiana University East, Richmod, Indiana [CT, Wed. 12:15, Room 4]

Matrix Optimization in Statistics

Statisticians have been dealing with matrix optimization problems which similar to Matrix Antieigenvalue problems. These problems occur in areas such as statistical efficiency and canonical correlations. Statisticians have generally took a variational approach to treat these matrix optimization problems. However, we will use the techniques we have developed for computation of Antieigenvalues to provide simpler solutions. Additionally, these techniques have enabled us to generalize some of the matrix optimization problems in statistics from positive matrices to normal accretive matrices and operators. One the techniques we use is a Two Nonzero Component Lema which is first proved by the author. Another technique is converting the Antieigenvalue problem to a convex programming problem. In the latter method the problem is reduced to finding the minimum of a convex function on the numerical range of an operator (which is a convex set).

Semrl, Peter, University of Ljubljana, Ljubljana, Slovenia [CT, Tue. 11:25, Room 3]

Locally linearly dependent operators

Let U and V be vector spaces. Linear operators T_{1}, …, T_{n} : U → V are locally linearly dependent if for every u ∈ U the vectors T_{1}u, …, T_{n}u are linearly dependent. Some recent results on such operators will be presented.

Sendov, Hristo, The University of Western Ontario, London, Canada [CT, Thu. 11:50, Room 3]

Spectral Manifolds

It is well known that the set of all n × n symmetric matrices of rank k is a smooth manifold. This set can be described as those symmetric matrices whose ordered vector of eigenvalues has exactly n − k zeros. The set of all vectors in ℝ^{n} with exactly n − k zero entries is itself an analytic manifold. In this work, we characterize the manifolds M in ℝ^{n} with the property that the set of all n × n symmetric matrices whose ordered vector of eigenvalues belongs to M is a manifold. In particular, we show that if M is a C^{2}, C^{∞}, or C^{ω} manifold then so is the corresponding matrix set. We give a formula for the dimension of the matrix manifold in terms of the dimension of M. (with A. Daniilidis, J. Malick, and A. Lewis)

Sergeev, Sergey, University of Birmingham, Birmingham, United Kingdom [MS7, Tue. 17:20, Room 3]

On Kleene stars and intersection of finitely generated semimodules

It is known that Kleene stars are fundamental objects in max-algebra and in other algebraic structures with idempotent addition. They play important role in solving classical problems in the spectral theory, and also in other respects. On the other hand, the approach of tropical convexity puts forward the tropical cellular decomposition, meaning that any tropical polytope (i.e., finitely generated semimodule) can be cut into a finite number of convex pieces, and subsequently treated as a cellular complex. We show that any convex piece of this complex is max-algebraic column span of a uniquely defined Kleene star. We provide some evidence that the tropical cellular decomposition can be used as a purely max-algebraic tool, with the main focus on the problem of finding a point in the intersection of several finitely generated semimodules.

Shader, Bryan, University of Wyoming, Laramie, US [MS1, Thu. 11:50, Room 1]

Average minimum rank of a graph

We establish asymptotic upper and lower bounds on the average minimum rank of a graph using probabilistic, linear algebraic and graph theoretic techniques. (with Francesco Barioli, Shaun Fallat, Tracy Hall, Daniel Hershkowitz, Leslie Hogben, Ryan Martin, and Hein van der Holst)

Shahryari, Mohammad, Tabriz University, Tabriz, Iran, Tabriz, Iran [CT, Thu. 12:15, Room 5]

Z_{2}-graded symmetry classes of tensors

In this paper, we define a natural ℤ_{2}-gradation on the symmetry class of tensors V_{χ}(G). We give the dimensions of even and odd parts of this gradation. Also we prove that the even part (the odd part) of this gradation is zero, if and only if the whole symmetry class is zero.

Shaked-Monderer, Naomi, Emek Yezreel College, Emek Yezreel, Israel [Plenary, Tue. 8:10–9:05]

Completely Positive Matrices and the CP-rank

A matrix A is completely positive if A = BB^{T} for some nonnegative matrix B. The minimum number of columns in such B is the cp-rank of A.

We review the main results on complete positivity and in particular re-examine results on the possible cp-ranks of completely positive matrices.

Singer, Ivan, Romanian Academy of Sciences, Bucharest, Romania [MS7, Wed. 10:35, Room 3]

Max-min convexity

The max-min semiring is the set \overline{R} = R ∪ \{−∞, +∞\} endowed with the operations ⊕ = max, ⊗ = min. We study the semimodule \overline{R}^{n} = \overline{R} × ... × \overline{R} (n times), with the operations ⊕ and ⊗ defined componentwise. A subset G of \overline{R}^{n} (respectively, a function f : \overline{R}^{n} → \overline{R}) is said to be max-min convex if the relations x, y ∈ G (respectively, x, y ∈ \overline{R}^{n}) and α, β ∈ \overline{R}, α ⊕ β = +∞, where +∞ is the neutral element for ⊗ = min, imply (α ⊗ x) ⊕ (β ⊗ y) ∈ G (respectively, f((α ⊗ x) ⊕ (β ⊗ y)) ≤ (α ⊗ f(x)) ⊕ (β ⊗ f(y)). We give some results on max-min convexity of sets and functions in \overline{R}^{n} (e.g. on segments, semispaces, separation, multi-order convexity, ...) that correspond to some results for max-plus convexity, replacing ⊗ = + of the max-plus case by the semi-group operation ⊗ = min of the max-min case.

References

K. Zimmermann, Convexity in semimodules. Ekonom.-Mat. Obzor 17 (1981), 199-213.

V. Nitica and I. Singer, Contributions to max-min convex geometry. I: Segments. Lin. Alg. Appl. 428 (2008), 1439-1459. II: Semispaces and convex sets. Ibidem 2085-2115.

Sinkovic, John, Technische Universiteit Eindhoven, Eindhoven, Netherlands [CT, Thu. 18:35, Room 3]

An upper bound for the maximum nullity of a symmetric matrix whose graph is outerplanar

Let G = (V, E) be a graph with V = {1, 2, …, n}. Define S(G, ℝ) as the set of all n×n real-valued symmetric matrices A = [a_{i,j}] with a_{i,j} ≠ 0, i ≠ j if and only if ij ∈ E. By M(G) we denote the largest possible nullity of any matrix A ∈ S(G). The path cover number of a graph G, denoted P (G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G. The path cover number of a graph G has been linked to the maximum nullity of G. It has been shown by Duarte and Johnson that for a tree T, P (T) = M(T). Barioli, Fallat, and Hogben have shown that for a unicyclic graph G, P (G) = M(G) or P (G) = M(G) + 1. In this talk I will show that for outerplanar graphs the path cover number is an upperbound for the maximum nullity and show that equality holds for partial 2-paths, which are outerplanar.

Sivic, Klemen, Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia [CT, Thu. 10:35, Room 4]

On varieties of commuting triples

The set C(3, n) of all triples of commuting n×n matrices over an algebraically closed field F is a variety in F^{3n^{2}} defined by 3n^{2} equations, which are relations of commutativity. The problem first proposed by Gerstenhaber asks to determine for which natural numbers n this varitey is irreducible. This is equivalent to the problem whether C(3, n) equals to the Zariski closure of the subset of all triples of generic matrices (i.e. matrices having n distinct eigenvalues). The answer is known to be positive for n ≤ 7 and negative for n ≥ 30. Using simultaneous commutative perturbations of pairs of matrices in the centralizer of the third matrix we prove that C(3, 8) is also irreducible.

Šmigoc, Helena, University College Dublin, Dublin, Ireland [MS8, Mon. 17:20, Room 1]

An example of constructing a nonnegative matrix with given spectrum

We say that a list of n complex numbers σ is the nonzero spectrum of a nonnegative matrix, if there exists a nonnegative integer N such that σ together with N zeros added to it is the spectrum of some (n + N) × (n + N) nonnegative matrix. Boyle and Handelman characterized all lists of n complex numbers that can be the nonzero spectrum of a nonnegative matrix. In this talk we will present a constructive proof that τ(t) = (3 + t, 3 − t, −2, −2, −2) is the nonzero spectrum of some nonnegative matrix for every t > 0. We will give a bound for the number of zeros that needs to be added to τ(t) to achieve a nonnegative realization. We will discuss how the method presented could be applied to more general situations. (with Laffey, Thomas)

Soares, Graça, University of Tras-os-Montes and Alto Douro, Vila Real, Portugal [CT, Mon. 17:45, Room 4]

Inequalities on an indefinite inner product space

We study some matrix inequalities on an indefinite inner product space, induced by a selfadjoint involution J, for J-selfadjoint matrices with non-negative eigenvalues. In particular, some characterizations of the J-chaotic order are obtained. (with N. Bebiano et al.)

Spitkovsky, Ilya, College of William and Mary, Blacksburg, VA, USA [Plenary, Fri. 9:10–10:05]

On the current state of the factorization problem for almost periodic matrix functions

Factorization of almost periodic matrix functions arises naturally in a variety of problems, both theoretical and applied, and for many of them the matrix in question is 2-by-2 and triangular. Even in this setting the factorability properties remain a mystery, in striking difference with both the scalar almost periodic case and with purely periodic matrix case. We will give a survey of available approaches to constructive factorization of matrices in question, and their relation to certain systems of linear equations.

Stefan, Wolfgang, Arizona State University, Tempe, Arizona [MS3, Fri. 11:25, Room 2]

Regularizing Least Squares with the Concentration Method

We present a novel deconvolution approach that simultaneously deblurs and detects edges in piecewise smooth signals. The edges and smooth regions, separated by jump discontinuities, are both preserved. The method uses a two step procedure: The polynomial annihilation edge detection method combined with total variation (TV) deconvolution obtains an estimate of the location of jump discontinuities in blurred noisy data. This information is used to determine the order for a higher-order TV regularization which is then utilized in the signal restoration. As compared to those obtained with standard first order TV, signal restorations are more accurate representations of the true signals, as measured in a relative l^{2} norm, and can also be used to obtain a more accurate estimation of the locations and sizes of the true jump discontinuities. (with Rosemary Renaut and Anne Gelb)

Stosic, Marko, Instituto de Sistemas e Robotica, IST, Lisbon, Portugal [CT, Mon. 12:25, Room 3]

On Generalized Procrustes Problem

In this talk we present a new approach to the generalized Procrustes problem: For given real matrices A ∈ ℝ^{n×3} and B ∈ ℝ^{n×2}, find the Stiefel matrix Q ∈ ℝ^{3×2} (i.e. such that Q^{T} Q = I_{2}), that minimizes the Frobenius norm of B − AQ. We rewrite this problem as the more general Quadratic Programming program, and give fast algorithm for its (partial) solutions. The solution is based on the computation of convex hulls of various sets of matrices. (with João Xavier)

Strong, David, Pepperdine University, Malibu, California, USA [MS4, Wed. 11:50, Room 2]

A Java Applet and Introductory Tutorial for the Jacobi, Gauss-Seidel and SOR Methods

I will discuss a Java applet, tutorial and exercises that are designed to allow both students and instructors to experiment with and visualize the Jacobi, Gauss-Seidel and SOR Methods in solving systems of linear equations. The applet is for working with 2 x 2 systems. The tutorial includes an analysis (using eigenvalues and spectral radius) of these methods. The exercises are designed to be done using the applet in order to more easily investigate ideas and issues that are often not dealt with when these methods are first introduced, but that are fundamental to numerical analysis and linear algebra, such as eigenvalues/vectors and convergence rates.

Stuart, Jeffrey, Pacific Lutheran University, Tacoma, USA [CT, Mon. 11:35, Room 4]

Spectrally Arbitrary Ray Patterns

An n × n ray pattern A is said to be spectrally arbitrary if for every monic n-th degree polynomial p(x) with complex coefficients, there is a complex matrix in the pattern class of A possessing p(x) as its characteristic polynomial. It is shown that every n × n irreducible, spectrally arbitrary ray pattern has at least 3n − 1 nonzero entries. A class of n × n irreducible, spectrally arbitrary ray patterns with exactly 3n nonzero entries for each integer n with n > 3 is exhibited. The main tool employed is the nilpotent Jacobi method, which previously has been used in the study of irreducible, spectrally arbitrary sign patterns.

Szyld, Daniel, Temple University, Phialdelphia, USA [MS8, Tue. 10:35, Room 2]

On General Matrices Having the Perron-Frobenius Property

We say that a matrix has the Perron-Frobenius property if its spectral radius is an eigenvalue for which there is an entry-wise nonnegative eigenvector. Matrices having the Perron-Frobenius property may be viewed as generalizations of nonnegative matrices. We consider spaces consisting of such generalized nonnegative matrices and study some of their topological aspects such as connectedness and closure. In addition, we completely describe the similarity transformations leaving such spaces invariant. We prove some new results needed for the analysis mentioned above, in which we show the existence of orthogonal matrices close to the identity which map semipositive vectors to positive ones. This new tool may be useful in other contexts as well. (with Elhashash, Abed)

Szyld, Daniel, Temple University, Phialdelphia, USA [MS8, Tue. 11:25, Room 2]

Convergence of Stationary Iterative Methods for Hermitian Semidefinite Linear Systems

A simple proof is presented of a quite general theorem on the convergence of stationary iterations for solving singular linear systems whose coefficient matrix is Hermitian and positive semidefinite. In this manner, elegant proofs are obtained of some known convergence results, including the necessity of the P -regular splitting result due to Keller, as well as recent results involving generalized inverses. Other generalizations are also presented. These results are then used to analyze the convergence of several versions of algebraic additive and multiplicative Schwarz methods for Hermitian positive semidefinite systems. (with Frommer, Andreas and Nabben, Reinhard)

Tam, Bit-Shun, University of Birmingham, Birmingham, UK [MS1, Fri. 16:45, Room 1]

Maximizing spectral radius of unoriented Laplacian matrix

For a (simple) graph G, by the unoriented Laplacian matrix of G we mean the matrix K(G) = D(G) + A(G), where A(G), D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. In this talk, I’ll report on recent progress in the problem of maximzing the spectral radius of the unoriented Laplacian matrix over various classes of graphs. Our treatment depends on the theory of threshold graphs, together with following new result: Let G be a graph. Let V_{1} …, V_{r} be the equivalence classes for the equivalence relation ∼ on V (G) defined by: u ∼ v if and only if N(u) \ {v} = N(v) \ {u}, where N(u) denotes the neighbor set of u in G. For j = 1, …, r, let n_{j} denote the cardinality of V_{j} and let δ_{j} be the common degree of the vertices in V_{j}. Let I_{1} (respectively, I_{2}) consist of all indices j such that n_{j} > 1 and G[V_{j}] is a null graph (respectively, a complete graph). For i, j = 1, …, r, let γ_{ij} equal 1 if there is an arc between V_{i} and V_{j} and equal 0, otherwise. Also, let B = (b_{ij}) denote the r × r matrix given by: b_{ij} equals γ_{ij}n_{j} for i ≠ j and equals γ_{ii}(n_{i} − 1) for i = j. Then the spectrum of K(G) is given by: σ(K(G)) = σ(Δ + B) ∪ {δ_{i}(n_{i} − 1 times : i ∈ I_{1}} ∪ {δ_{i} − 1(n_{i} − 1) times : i ∈ I_{2}}, where Δ = diag(δ_{1}, …, δ_{r}). (with Ding-Jung Chang and Shui-Hei Wu)

Tanguay, Denis, Université du Québec à Montréal (UQAM), Montréal, Canada [MS4, Tue. 17:45, Room 1]

A fundamental paradox in learning algebra

The generalizing, formalizing and unifying nature of some of the concepts of Linear Algebra leads to a high level of abstraction, which in turn constitutes a source of difficulties for students. When asked to deal with new expressions, new symbolism and rules of calculation, students face what researchers in mathematics education — such as Dorier, Rogalski, Sierpinska or Harel — have identified as ‘the obstacle of formalism’.

Teachers bring in new mathematical objects, sometimes in a non explicit way, by using at once the symbols referring to these objects or to the related relations, without explaining or justifying the meaning or the relevance of their choices, regarding this new symbolism. Calculations and manipulations with these new objects build up to new algebras (vector or matrix algebras) more complex than basic (high school) algebra, but nevertheless syntactically modelled on it. The gap thus caused reveals itself when students bring out inconsistent or meaningless writings : “The obstacle of formalism manifests itself in students who operate at the level of the form of expressions without seeing these expressions as referring to something other than themselves. One of the symptoms is the confusion between categories of mathematical objects; for example, sets are treated as elements of sets, transformations as vectors, relations as equations, vectors as numbers, and so on” (Sierpinska et al., 1999, p. 12). For too many students attending their first course in Linear Algebra, the latter is nothing but a catalogue of very abstract notions, for which they have almost no understanding, being overwhelmed by a flood of new words, new symbols, new definitions and new theorems (Dorier, 1997).

Our talk will be based on a study conducted within the context of a master degree in mathematics education (maîtrise en didactique des mathématiques, Université du Québec à Montréal ; cf. Corriveau & Tanguay, 2007). Through this study, we tried to have a better understanding of transitional difficulties, due to the abrupt increase in what is expected from students with respect to formalism and proof, when going from Secondary schools to ‘Cegeps’ (equivalent in Québec of ‘upper secondary’ or ‘high-school’, 17-19 years of age). The Linear Algebra courses having been identified as those in which such transitional problems are the most acute, we first selected, among all problems submitted in a given L. A. course — the teacher of which was ready to participate in the study — those involving a proof or a reasoning at least partly deductive.

Through the systematic analysis of these problems, we evaluated and compared their level of difficulty, as well as students’ preparation for coping with such difficulties, from an ‘introduction-to-formalism’ perspective. The framework used to analyse the problems stemmed from a remodelling of Robert’s framework (1998). The remodelling was a consequence of having compared/confronted an a priori analysis of three problems (using Robert’s framework), with the analysis of their erroneous solutions as they appeared in twelve students’ homework copies.

Among the conclusions brought up by the study, we shall be interested in the following ones

• Mathematical formalism allows a ‘compression’ of the mathematical discourse, simplification and systematization of the syntax, by which one operates on this discourse with better efficiency. But this improvement in efficiency is achieved to the detriment of meaning. As in Bloch and al. (2007), the study confirms that “...formal written discourse does not carry per se the meaning of neither the laws that it states nor the objects that it sets forth.” For many students, symbolic manipulations are difficult in Linear Algebra because meaning has been lost somewhere. By trying to have a better understanding of the underlying obstacle, we came to identify what we call ‘the fundamental paradox in learning [a new] algebra’, some elements of which will be discussed further in the talk.

• The analysis of students’ written productions brings us to observe that in the process of proving, difficulties caused by the introduction of new objects and new rules of calculation on the one hand, and difficulties related to controlling the deductive reasoning and its logical structure on the other, are reinforcing one another.

• A better understanding of students’ errors, by an error-analysis such as the one done in the study, allows a better evaluation of the difficulty level of what is asked to students, and thus a better understanding of the problems linked to academic transitions (from lower-secondary to upper-secondary to university) in mathematics. Such analyses could give Linear Algebra teachers better tools, for estimating the difficulties in the tasks they submit to their students, as well as for understanding the underlying cognitive gaps and ruptures. It would be advisable that teachers be introduced to such error-analysis work, in the setting of their pre-service or in-service instruction.

Bloch, I., Kientega, G. & Tanguay, D. (2007). Synthèse du Thème 6 : Transition secondaire / postsecondaire et enseignement des mathématiques dans le postsecondaire. To appear in Actes du Colloque EMF 2006. Université de Sherbrooke.

Corriveau, C. & Tanguay, D. (2007). Formalisme accru du secondaire au collégial : les cours d’Algèbre linéaire comme indicateurs. To appear in Bulletin AMQ, Vol. XLVII, n^{∘}4.

Dorier, J.-L., Harel, G., Hillel, J., Rogalski, M., Robinet, J., Robert, A. & Sierpinska, A. (1997). L’enseignement de l’algèbre linéaire en question. J.-L. Dorier, ed. La Pensée Sauvage. Grenoble, France.

Harel, G. (1990). Using Geometric Models and Vector Arithmetic to Teach High-School Students Basic Notions in Linear Algebra. International Journal of Mathematical Education in Science and Technology, Vol 21, n^{∘}3, pp. 387-392.

Harel, G. (1989). Learning and Teaching Linear Algebra : Difficulties and an Alternative Approach to Visualizing Concepts and Processes. Focus on Learning Problems in Mathematics, Vol. 11, n^{∘}2, pp. 139-148.

Robert, A. (1998). Outils d’analyse des contenus mathématiques à enseigner au lycée et à l’université. Recherches en didactique des mathématiques, vol. 18, n^{∘}2, pp. 139-190.

Rogalski, M. (1990). Pourquoi un tel échec de l’enseignement de l’algèbre linéaire ? In Enseigner autrement les mathématiques en DEUG Première Année, Commission inter-IREM université (ed.), pp. 279-291. IREM de Lyon.

Sierpinska, A., Dreyfus, T. & Hillel, J. (1999). Evaluation of a Teaching Design in Linear Algebra : the Case of Linear Transformations. Recherches en didactiques des mathématiques, Vol. 19, n^{∘}1, pp. 7-40. (with Corriveau, Claudia)

Teixeira Matos, Isabel, Centro de Estruturas Lineares e Combinatórias (CELC), Lisboa, Portugal [CT, Fri. 15:55, Room 3]

A Completion Problem over the Field of Real Numbers

Let F be a field. In 1975 G. N. de Oliveira has proposed the following completion problems: Describe the possible characteristic polynomials of

[ \begin{matrix}A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{matrix} ] ,

where A_{1,1} and A_{2,2} are square submatrices, when some of the blocks A_{i,j} are fixed and the others vary. Several of these problems remain unsolved. We give the solution, over the field of real numbers, of Oliveira’s problem where the blocks A_{1,2}, A_{2,1} are fixed and the others vary. (with Fernando C. Silva)

Trigueros, María, Depto de Matemáticas ITAM, México DF, México [MS4, Mon. 12:25, Room 1]

Spanning sets and vector spaces they generate: an APOS analysis

This work forms part of a larger research project that aims to identify student difficulties with Linear Algebra concepts. The theoretical framework that we have chosen for this particular study is APOS (Action — Process — Object — Schema) theory, whose efficiency in identifying students’ mental constructions is well documented in other areas of mathematics such as Calculus, Abstract Algebra and Discrete Mathematics. In our previous work (Kú et al., submitted) in looking into the mental constructions in relation with the concept of basis, we came across various difficulties that students experienced with spanning sets and the vector spaces they generate. Our results revealed that most of the interviewed students had an action or process conception of this concept. When comparing the empirical data with the genetic decomposition originally proposed for this concept, where the concepts of linear independence and generator set had been considered, it appeared that most of the obstacles had to do with what seemed to be necessary conditions to construct the notion of spanning set as a process. In this talk we present a study that intends to study the construction of the notion of spanning set and its relation with the vector space concept. A preliminary genetic decomposition for this concept was developed and instruments were designed according to this genetic theoretical analysis. We will present the analysis of the interviews that were conducted with students taking a Linear Algebra course. We will discuss and interpret results in terms of APOS theory. (with Ku, Darly and Oktaç, Asuman)

Uchiyama, Mitsuru, Shimane University, Matsue, Shimane, Japan [CT, Mon. 18:10, Room 4]

A New Majorization between functions

Let {a_{i}}_{i=1}^{n} and {b_{i}}_{i=1}^{n} be finite sets of real numbers, and rearrange them in decreasing order. Then {a_{i}}_{i=1}^{n} is said to be submajorized by {b_{i}}_{i=1}^{n} if ∑_{i=1}^{k} a_{i} ≦ ∑_{i=1}^{k} b_{i} for 1 ≦ k ≦ n. This classical concept -(sub)majorization- is very useful in the study of polynomials and matrices. Definition. For a real increasing function k on interval J and a nondecreasing function h on I, we call k a majorization of h and denote h ⪯ k if k(A) ≦ k(B) ⟹ h(A) ≦ h(B). A function f(t) defined on an interval I is called an operator monotone function on I, provided A ≦ B implies f(A) ≦ f(B) for every pair A and B. ℙ(I) denotes the set of all operator monotone functions on I, ℙ_{+}(I) does {f ∈ ℙ(I) : f ≧ 0}. 𝕃ℙ_{+}(I) := {h : h(t) > 0 and log h ∈ ℙ(I^{∘})}.

ℙ_{+}^{−1}[a, b) := {h|h is increasing on [a, b) and h^{−1} ∈ ℙ[0, ∞)}. ℙ_{+}^{−1}(a, b) is likewise defined. Theorem 1. For non-increasing sequences {a_{i}}_{i=1}^{n} and {b_{i}}_{i=1}^{m}, u(t) := ∏_{i=1}^{n}(t − a_{i}) (t ≧ a_{1}), v(t) := ∏_{i=1}^{m}(t − b_{i}) (t ≧ b_{1}). Then u(t) ∈ ℙ_{+}^{−1}[a_{1}, ∞), and

m ≦ n, ∑_{i=1}^{k} b_{i} ≦ ∑_{i=1}^{k} a_{i} (1 ≦ k ≦ m) ⟹ v ⪯ u ([a_{1}, ∞)).

Product Lemma. Let I be a right open interval with end points a, b and h(t), g(t) non-negative functions defined on I such that the product hg is an increasing function with hg(a + 0) = 0, hg(b − 0) = ∞. Then for ψ_{1}, ψ_{2} in ℙ_{+}[0, ∞)

g ⪯ hg ⟹ h ⪯ hg, ψ_{1}(h)ψ_{2}(g) ⪯ hg.

Product Theorem. For every right open interval I,

ℙ_{+}^{−1}(I) · ℙ_{+}^{−1}(I) ⊂ ℙ_{+}^{−1}(I), 𝕃ℙ_{+}(I) · ℙ_{+}^{−1}(I) ⊂ ℙ_{+}^{−1}(I).

Further, let g_{i}(t) ∈ 𝕃ℙ_{+}(I) for 1 ≦ i ≦ m and h_{j}(t) ∈ ℙ_{+}^{−1}(I) for 1 ≦ j ≦ n. Then for ψ_{i}, ϕ_{j} ∈ ℙ_{+}[0, ∞)

∏_{i=1}^{m} ψ_{i}(g_{i}) ∏_{j=1}^{n} ϕ_{j}(h_{j}) ⪯ ∏_{i=1}^{m} g_{i} ∏_{j=1}^{n} h_{j}.

Proposition. For 0 < β ≦ α,

t^{α} ⪯ t^{α}e^{−t^{−β}}.

Moreover, if 1 ≦ α, then

t^{α}e^{−t^{−β}} ∈ ℙ_{+}^{−1}[0, ∞).

Theorem 2. Let I be a right open interval, h(t) ∈ ℙ_{+}^{−1}(I), g(t) ∈ 𝕃ℙ_{+}(I), and let h̃(t) ≧ 0 be non-decreasing function on I. Then the function φ on (0, ∞) defined by

φ(g(t)h(t)) = g(t)h̃(t) (t ∈ I)

belongs to ℙ_{+}[0, ∞), and for A, B with σ(A), σ(B) ⊂ I

A ≦ B ⇒ \{ \begin{matrix}φ(g(A)^{\frac{1}{2}} h(B)g(A)^{\frac{1}{2}} ) ≧ g(A)^{\frac{1}{2}} h̃(B)g(A)^{\frac{1}{2}} , \\ φ(g(B)^{\frac{1}{2}} h(A)g(B)^{\frac{1}{2}} ) ≦ g(B)^{\frac{1}{2}} h̃(A)g(B)^{\frac{1}{2}} . \end{matrix}

Furthermore, if h̃ ∈ ℙ_{+}(I), then

A ≦ B ⇒ \{ \begin{matrix}φ(g(A)^{\frac{1}{2}} h(B)g(A)^{\frac{1}{2}} ) ≧ φ(g(A)^{\frac{1}{2}} h(A)g(A)^{\frac{1}{2}} ) = g(A)h̃(A), \\ φ(g(B)^{\frac{1}{2}} h(A)g(B)^{\frac{1}{2}} ) ≦ φ(g(B)^{\frac{1}{2}} h(B)g(B)^{\frac{1}{2}} ) = g(B)h̃(B). \end{matrix}

Corollary 1.(Furuta) For p ≧ 1, r > 0

0 ≦ A ≦ B ⇒ \{ \begin{matrix}(A^{\frac{r}{2}} B^{p}A^{\frac{r}{2}} )^{\frac{1+r}{p+r}} ≧ (A^{\frac{r}{2}} A^{p}A^{\frac{r}{2}} )^{\frac{1+r}{p+r}} , \\ (B^{\frac{r}{2}} A^{p}B^{\frac{r}{2}} )^{\frac{1+r}{p+r}} ≦ (B^{\frac{r}{2}} B^{p}B^{\frac{r}{2}} )^{\frac{1+r}{p+r}} . \end{matrix}

Corollary 2. (Ando, F-F-K, U) Suppose p ≧ 1, r > 0 and 0 < α ≦ \frac{r}{p+r}. Then

A ≦ B ⇒ \{ \begin{matrix}(e^{\frac{r}{2} A}e^{pB}e^{\frac{r}{2} A})^{\frac{r}{p+r}} ≧ (e^{\frac{r}{2} A}e^{pA}e^{\frac{r}{2} A})^{\frac{r}{p+r}} , \\ (e^{\frac{r}{2} B}e^{pA}e^{\frac{r}{2} B})^{\frac{r}{p+r}} ≦ (e^{\frac{r}{2} B}e^{pB}e^{\frac{r}{2} B})^{\frac{r}{p+r}} . \end{matrix}

References: M. Uchiyama, A new majorization between functions, polynomials, and operator inequalities, J.F.A(2006)221– 244, M. Uchiyama, A new majorization between functions, polynomials, and operator inequalities II, J. Math. Soc. Japan (2008) 291–310.

Uhlig, Frank, Mathematics, Auburn University, Auburn, AL 36849, USA [CT, Wed. 10:35, Room 4]

Convex and Non-convex Optimization Problems for the Field of Values of a Matrix

We introduce and study numerical algorithms that compute the minimal and maximal distances between 0 ∈ ℂ and points in the field of values F (A) = {x^{∗}Ax | x ∈ ℂ^{n} , ∥x∥_{2} = 1} ⊂ ℂ for a complex matrix A_{n,n}. Finding the minimal distance from 0 ∈ ℂ to F (A) is a convex optimization problem if 0 ∉ F (A) and thus it has a unique solution, called the Crawford number whose magnitude relates information on the stability margin of the associated system. If 0 ∈ F (A), this is a non-convex optimization problem and consequently there can be multiple solutions or local minima that are not so globally. Non-convexity also holds for the maximal distance problem between points in F (A) and 0 ∈ ℂ. This maximal distance is commonly called the numerical radius numrad(A) for which the inequality ρ(A) ≤ numrad(A) ≤ ∥A∥ is well established. Both cases can be solved efficiently numerically by using ideas from geometric computing, eigenanalyses of linear combinations of the hermitean and skew-hermitean parts of A and the rotation method introduced by C. R. Johnson in the 1970s to compute the boundary of the field of values.

Vallejo, Ernesto, Instituto de Matemáticas, Morelia, México [CT, Mon. 12:25, Room 4]

Additivity obstructions for integral matrices and pyramids

There are two important notions in Discrete Tomography: uniqueness and additivity. A finite set S of lattice points in 3-dimensional euclidean space is called a set of uniqueness if it is uniquely determined by the cardinalities of the intersections of S with the planes parallel to the coordinate planes. The additivity condition is an auxiliary one and is sufficient for uniqueness but not necessary. Fisburn, Lagarias, Reeds and Shepp gave complete lists of obstructions for uniqueness (bad configurations) and for additivity (weakly bad configurations). They raised the following question: Is there an upper bound on the weights of the bad configurations one needs to consider to determine uniqueness of an arbitrary set S? A similar question can be asked for additivity. For example, if one considers lattice sets in 2-dimensional euclidean space, one can consider uniqueness and additivity with respect to lines parallel to the coordinate axes. In this case only bad configurations of weight 2 are needed to determine uniqueness (this result goes back to Ryser). In this talk que answer the question of Fishburn et al. and show that there is no upper bound on the weights of the bad configurations one needs to consider to determine uniqueness (as defined above) and additivity of finite lattice sets in 3-dimensional space. (with Miguel Santoyo)

van den Driessche, Pauline, University of Victoria, Victoria, Canada [MS7, Mon. 11:10, Room 2]

Bounds for the Perron root using max eigenvalues

Using the techniques of max algebra, a new proof of Al’pin’s lower and upper bounds for the Perron root of a nonnegative matrix is given. The bounds depend on the row sums of the matrix and its directed graph. If the matrix has zero diagonal entries, then these bounds may improve the classical row sum bounds. This is illustrated by a generalized tournament matrix. (with Elsner, Ludwig)

van der Holst, Hein, Eindhoven University of Technology, Eindhoven, The Netherlands [MS1, Thu. 11:00, Room 1]

Computing the minimum rank of partial 2-trees

A 2-tree is recursively defined as follows: the complete graph on three vertices is a 2-tree, and if we have a 2-tree, a larger can be obtained by adding a new vertex adjacent to the endpoints of an edge in the 2-tree. A partial 2-tree is a subgraph of a 2-tree. The minimum rank of a graph G is the smallest rank over all symmetric matrices A = [a_{i,j}] with a_{i,j} ≠ 0, i ≠ j if and only if ij is an edge of G. In this talk, I present an efficient algorithm to compute the minimum rank of a partial 2-tree, and show how it can be extended to compute other minimum rank-type problems.

Vander Meulen, Kevin, Redeemer University College, Ancaster, Ontario, Canada [MS1, Fri. 15:55, Room 1]

Sparse Inertially Arbitrary Sign Patterns

The inertia of a real matrix A is an ordered triple i(A) = (n_{1}, n_{2}, n_{3}) where n_{1} is the number of eigenvalues of A with positive real part, n_{2} is the number of eigenvalues of A with negative real part, and n_{3} is the number of eigenvalues of A with zero real part. A sign pattern is a matrix whose entries are in {+, −, 0}. An order n sign pattern S is inertially arbitrary if for every ordered triple (n_{1}, n_{2}, n_{3}) with n_{1} + n_{2} + n_{3} = n there is a real matrix A such that A has sign pattern S and i(A) = (n_{1}, n_{2}, n_{3}). We describe some techniques in determining a pattern is inertially arbitrary. We present some irreducible inertially arbitrary patterns of order n with less than 2n entries. (with L. Vanderspek and M. Cavers)

Van Dooren, Paul, Université catholique de Louvain, Louvain-la-Neuve, Belgium [Plenary, Thu. 9:10–10:05]

Some graph optimization problems in data mining

Graph-theoretic ideas have become very useful in uderstanding modern large-scale datamining techniques. We show in this talk that ideas from optimization are also quite useful to better understand the numerical behaviour of the corresponding algorithms. We illustrate this claim by looking at two specific graph theoretic problems and their application in datamining. The first problem is that of reputation systems where the reputation of objects and voters on the web are estimated; the second problem is that of estimating the similarity of nodes of large graphs. These two problems are also illustrated using concrete applications in datamining.

Van Dooren, Paul, Université catholique de Louvain, Louvain-la-Neuve, Belgium [MS5, Thu. 11:00, Room 2]

H2 Approximation and Tangential Rational Interpolation

We consider the problem of approximating an m×p rational transfer function H(s) of high degree by another m × p rational transfer function Ĥ(s) of much smaller degree. We derive the gradients of the H_{∈}-norm of the approximation error and show how this can be solved via tangential interpolation. We then extend these results to the discrete-time case, for both time-invariant and time-varying systems. (with K. Gallivan and P.A. Absil)

Vargas, Xaab Nop, ICYTDF, México, México [CT, Mon. 17:45, Room 2]

Students difficulties with the concept of vector space from point of view of APOS Theory

Vector space theory, being abstract in nature and having an epistemological status different from most mathematical topics taught at the undergraduate level, is a major source of difficulty for beginning linear algebra students (Dorier, 1995a; Dorier, 1995b). The identification of the nature of these difficulties and their association with the way in which students construct the concept of vector spaces is of great importance on the way to the development and implementation of good instructional strategies. APOS (Action-Process-Object-Schema) Theory provides a research tool that has been successfully used in other areas of mathematics such as abstract algebra and calculus, for similar purposes. In a previous paper (Trigueros and Oktac, 2005) a possible genetic decomposition for the concept of vector spaces was reported, and activities that were designed in such a way that students can make the necessary mental constructions required by the genetic decomposition of the concept were analyzed. Taking into account this paper, an instrument to conduct a semi-structured interview was designed using our theoretical framework, to be applied to a selected group of students. The data from the interviews will be analyzed using the same framework. The interview consisted of 17 questions about the concepts of vector space and subspace. Here we present two of these questions (numbered 1 and 2 in the instrument), together with our a priori analysis of them and related student performance.

References:

Dorier, J-L. (1995a): A general outline of the genesis of vector space theory. Historia Mathematica, 22(3), 227-261.

Dorier, J-L. (1995b): Meta level in the teaching of unifying and generalizing concepts in mathematics. Educational Studies in Mathematics, 29(2), 175-197.

Trigueros, M. and Oktac, A. (2005): La Théorie APOS et l’Enseignement de l’Algebre Lineaire. Annales de Didactique et de Sciences Cognitives, vol. 10, 157-176.

Verde-Star, Luis, UAM Iztapalapa, México DF, México [CT, Fri. 12:15, Room 4]

Linear algebraic approach to rational functions

We consider some basic linear algebraic aspects of the algebra of rational functions in one complex variable. We also look at some duality properties and the Hopf algebra structure, and show that there are other important algebras that are isomorphic to the rational functions.

Vieira, Luis, Feup, Porto, Portugal [CT, Mon. 18:35, Room 2]

Euclidean Jordan algebras and inequalities on the parameters and on the spectra of a strongly regular graph

Let τ be a strongly (n, p; a, c) regular graph, such that 0 < c < p < n − 1, A his matrix of adjacency and let V_{n} be the Euclidean real space spanned by the powers A^{j}, j ∈ ℕ_{0} where the scalar product •|• is defined by x|y = trace(x · y). In this exposition one proves that V_{n} is an Euclidean Jordan algebra of rank 3 when one introduces in V_{n} the usual product of matrices. Working inside the Euclidean Jordan algebra V_{n} with the the only complete system of orthogonal idempotents associated to A one defines the generalized Krein parameters of the strongly (n, p; a, c) regular graph τ. Finally one presents necessary conditions over the parameters and the spectra of the strongly (n, p; a, c) regular graph τ.

Weaver, James, University of West Florida, Pensacola, FL 32514, USA [CT, Mon. 12:00, Room 4]

Nonsingularity of Divisor Tournaments

Matrix theoretic properties and examples of divisor tournaments are discussed. Emphasis is placed on results and conjectures about the nonsingularity of the adjacency matrix for a divisor tournament. Definition 1 For an integer n > 2, the divisor tournament D(T_{n}) ( a directed graph on the vertices 2, 3, …, n) is defined by: i is adjacent to j if i divides j, otherwise j is adjacent to i for 2 ≤ i < j ≤ n. No vertex is adjacent to itself. Definitioni 2 The adjacency matrix T_{n} of the directed graph D(T_{n}) with vertex set {2, 3, …, n} is the (n − 1) × (n − 1) matrix [t_{ij}] defined by t_{ij} = 1 and t_{ji} = 0 if i | j, t_{ij} = 0 and t_{ji} = 1 if i |̸ j for 2 ≤ i < j ≤ n. t_{ii} = 0 for i ∈ {2, 3, …, n}. (with Rohan Hemasinha and Jeffrey L. Stuart)

Wojciechowski, Piotr, University of Texas at El Paso, El Paso, USA [CT, Fri. 16:45, Room 3]

Orderings of matrix algebras and their applications

The full matrix algebra M_{n}(F) over a totally-ordered subfield F of the reals becomes a partially ordered algebra by a partial order relation ≤ on the set M_{n}(F), if for any A, B, C ∈ M_{n}(F) from A ≤ B it follows that:

(1) A + C ≤ B + C

(2) if C ≥ 0 then AC ≤ BC and CA ≤ CB

(3) if F ∋ α ≥ 0 then αA ≤ αB.

Our interest is when the order ≤ is a lattice or at least is directed. Then we have a lattice-ordered algebra of matrices or a directly-ordered algebra of matrices. Those concepts originate in 1956 in Birkhoff and Pierce in [1]. The first example of a lattice-ordered algebra of matrices is, of course, with the usual entry-wise ordering. In this ordering the identity matrix I is positive. In 1966 E. Weinberg proved in [6] that the positivity of I forces a lattice-ordering to be (isomorphic to) the usual one in M_{2}(F) and conjectured the same for all n ≥ 2. The conjecture was positively solved in 2002 by J. Ma and P. Wojciechowski in [4]. The proof involved a cone-theoretic approach, by first establishing existence of a P -invariant cone O in F^{n}, i.e. satisfying the condition that for every matrix M ∈ P, M(O) ⊆ O, where P is the positive cone of the ordering ≤ (P = {A ∈ M_{n}(F) : A ≥ 0}.) With help of compactness of a unit sphere in R^{n} and the Zorn’s Lemma, we obtained all the desired properties of the cone O that led us to the conclusion of the conjecture.

The first part of the talk will briefly outline the method.

The above considerations allowed us to comprehensively describe all lattice orders of M_{n}(F) (J. Ma and P. Wojciechowski [5]): the algebra M_{n}(F) is lattice-ordered (within an isomorphism) if and only if

A ≥ 0 ⇔ A = ∑_{i,j=1}^{n} α_{ij}E_{ij}H^{T}

with

α_{ij} ≥ 0

i, j = 1, …, n, for some given H nonsingular with nonnegative entries and E_{ij} having 1 in the ij entry and zeros elsewhere.

As a first application, we will describe all multiplicative bases in the matrix algebra M_{n}(F) and provide their enumeration for small n (C. De La Mora and P. Wojciechowski 2006 [2].) In a finite-dimensional algebra over a field F, a basis 𝔅 is called a multiplicative basis provided that 𝔅 ∪ {0} forms a semigroup. Although these bases (endowed with some additional algebraic properties) have been studied in the representation theory, they lacked a comprehensive classification for matrix algebras. The first example of a multiplicative basis of M_{n}(F) should of course be {E_{ij}, i, j = 1, …, n}. Every lattice order on M_{n}(F) corresponds to a nonsingular n × n matrix H with nonnegative entries. It turns out that if the entries are either 0 or 1, the basic matrices resulting in the definition of the lattice order, i.e. the matrices E_{ij}H^{T} form a multiplicative basis, and conversely, every multiplicative basis corresponds to a nonsingular zero-one matrix. After identification of the isomorphic semigroups and also identification of the matrices that have just permuted rows and columns, the above correspondence is one-to-one. The number of zero-one nonsingular matrices, although lacking a formula so far, is known for a few small n values. This, together with the conjugacy class method from group theory, allowed us to calculate the number of nonequivalent multiplicative bases up to dimension 5: 1, 2, 8, 61, 1153.

Another application concerns certain directed partial orders of matrices that appear naturally in linear algebra and its applications. It is related to the research of matrices preserving cones, established in the seventies, among others by R. Loewy and H. Schneider in [3]. Besides the lattice orders (corresponding to the simplicial cones), the best studied ones are the orders whose positive cones are the sets Π(O), of all matrices preserving a regular (or full) cone O in an n-dimensional Euclidean space. It can be shown that O is essentially the only Π(O)-invariant cone (P. Wojciechowski [7].) Consequently, we obtain a characterization of all maximal directed partial orders on the n × n matrix algebra: a directed order is maximal if and only if its positive cone P satisfies P = Π(O) for some regular cone O. The method used in the proof involves a concept of simplicial separation, allowing a regular cone to be separated from an outside point by means of a simplicial cone.

Some open questions related to the discussed topics will be raised during the talk.

References

[1] G. Birkhoff and R.S. Pierce, Lattice-ordered rings, An. Acad. Brasil. Ci. 28 (1956), 41-69.

[2] C. de La Mora and P. Wojciechowski Multiplicative bases in matrix algebras, Linear Algebra and Applications 419 (2006) 287-298.

[3] R. Loewy and H. Schneider, Positive Operators on the n-dimensional Ice-Cream Cone, J. Math. Anal. Appl. 49 (1975)

[4] J. Ma and P. Wojciechowski, A proof of Weinberg’s conjecture on lattice-ordered matrix algebras, Pro. Amer. Math. Soc., 130(2002), no. 10, 2845-2851.

[5] J. Ma and P. Wojciechowski, Lattice orders on matrix algebras, Algebra Univers. 47 (2002), 435-441.

[6] E. C. Weinberg, On the scarcity of lattice-ordered matrix rings, Pacific J. Math. 19 (1966), 561-571.

[7] P. Wojciechowski Directed maximal partial orders of matrices, Linear Algebra and Applications 375(2003) 45-49

Wrobel, Iwona, Warsaw University of Technology and Polish Academy of Sciences, Warsaw, Poland [CT, Thu. 10:35, Room 3]

The Gauss-Lucas theorem and the numerical range

The Gauss-Lucas theorem states that the convex hull of the roots of a given complex polynomial contains the roots of its derivative. We will discuss possibilities of generalizing this result to the numerical range of companion matrices.

Wu, Pei Yuan, National Chiao Tung University, Hsinchu, Taiwan [CT, Wed. 11:25, Room 4]

Numerical ranges of nilpotent operators

For any operator A on a Hilbert space, let w(A) and w_{0}(A) denote its numerical radius and the distance from the origin to the boundary of its numerical range, respectively. We prove that if A is nilpotent with nilpotency n, then w(A) is at most the product of n − 1 and w_{0}(A). When A attains its numerical radius, we also determine a necessary and sufficient condition for the equality to hold. (with Hwa-Long Gau)

Zandieh, Michelle, Arizona State University, Tempe, AZ, USA [MS4, Wed. 11:00, Room 2]

Design of a unit to teach eigenvectors and eigenvalues based on the instructional design principles of Realistic Mathematics Education

An understanding of eigen theory can provide students with powerful ways of analyzing and understanding systemic-level problems in many areas of mathematics, engineering, and sciences.

Most mathematics, engineering, and physics majors will encounter eigen theory at least twice in their undergraduate career: in linear algebra and in differential equations. Prior research documents the many struggles that students face as they attempt to bridge their informal and intuitive ways of thinking with the formalization of concepts in linear algebra (Dorier, Robert, Robinet and Rogalski, 2000; Carlson, 1993). Contemporary theories of learning and advances in instructional design theory, however, offer fresh ideas for addressing these well-documented problems.

The purpose of this paper is to report on one such research-based approach to improve the learning and teaching of linear algebra. In particular, this paper will articulate a hypothetical learning trajectory (HLT) for the development of eigen theory. This HLT will be grounded in analysis of data collected from a semester long teaching experiment in linear algebra. As such, the HLT we describe will be both retrospective and prospective. It will be retrospective in the sense that the HLT is informed not only by the literature, but also by our ongoing work with learners. It is prospective in the sense that what we learned from working with students informs revisions and changes to our HLT. This, in turn, will be the basis for our next classroom teaching experiment.

We define a HLT to be a storyline about teaching and learning that occurs over an extended period of time (cf, Simon, 1995). The storyline includes four aspects, all of which are reflexively related and revisable:

(1) Learning goals about student reasoning, (2) a storyline of how students’ mathematical learning experience will evolve, (3) the role of the teacher in the storyline, and (4) a sequence of instructional tasks that students will engage in. In our view, a HLT can be a useful tool for researchers and instructional designers interested in studying the evolution of student reasoning in classroom settings.

Our instructional design efforts are informed in large part by the theory of Realistic Mathematics Education (RME), with particular emphasis on the heuristics of guided reinvention and emergent models (Gravemeijer, 1999). The heuristic of guided reinvention suggests means by which teachers and instructional designers can promote students’ ability to develop the intended mathematics for themselves. The emphasis of guided reinvention is on the character of the learning process, rather than on inventing as such. The heuristic of emergent models can be thought of in terms of a global transition in which students and the teacher develop a model-of their informal activity which gradually develops into a model-for more formal mathematical reasoning. This global transition is a process by which a new mathematical reality emerges, grounded in informal and situation-specific activity (Zandieh & Rasmussen, 2008).

For example, in our teaching experiment we found that students could essentially reinvent the determinant as a way of measuring the area of the image of the unit square under multiplication by an arbitrary 2x2 matrix. More importantly, and related to the notion of emergent models, the relationship between the column vectors of a matrix and the determinant of this matrix has the potential to become a powerful reasoning tool.

Figure 1: A student shows how he found the area.

Figure 1 gives one student’s work on a task that asked them to find an expression for the area of the image

of the unit square when multiplied by the matrix (\begin{matrix}a & b \\ c & d \end{matrix}).

After finding this area, students were then asked to make predictions about the area of the image of a unit square when multiplied by a 2x2 matrix whose column vectors were linearly dependent. This helped students to develop a visual intuition for the relationship between the determinant of a matrix and the linear (in)dependence of the column vectors that make up the matrix. Nearly a month after this introduction to determinants, one student, who we will call Karl, explained his thinking about how this idea connects to eigen theory:

When you look at the, uh, vectors, what does the determinant give us? It gives us the area between any two given vectors. And if, if our determinant equals zero, that basically means that the vectors that we’re solving for have no area in between. So therefore they lie along the same line.

As he spoke, Karl held his hands in a v-shape, presumably emulating two vectors pointing out from the origin. When he made reference to the determinant being zero, he made a motion of flattening his hands together to indicate that the two vectors now lie along the same line.

This type of reasoning has inspired us to reframe the development of the eigen unit. In particular, we conjecture that it might be more intuitive for students to first think about the process of finding eigenvectors, as opposed to eigenvalues. This “eigenvector first” approach goes along with the goal to find those vectors whose image lies along the same line as the original vector – and these vectors can be found by forcing the determinant to be zero. Such an eigenvector first approach has also been documented to be more conceptually accessible to student in differential equations (Rasmussen & Blumenfeld, 2007). Our full paper will detail the four components (Learning goals about student reasoning, a storyline of how students’ mathematical learning experience will evolve, the role of the teacher in the storyline, and a sequence of instructional tasks) for our new HLT for this innovative “eigenvector first” approach.

References

Carlson, D. (1993). Teaching linear algebra: Must the fog always roll in? The College Mathematical Journal, 24(1), 29-40.

Dorier, J.L., Robers, A., Robinet, J., & Rogalski, M. (2000). The obstacles of formalism in linear algebra. In J.L. Dorier (Ed.), On the teaching of linear algebra (pp. 85-124). Dordrecht: Kluwer.

Gravemeijer, K. (1999). How emergent models may foster the constitution of formal mathematics. Mathematical Thinking and Learning, 1, 155-177.

Rasmussen, C., & Blumenfeld, H. (2007). Reinventing solutions to systems of linear differential equations: A case of emergent models involving analytic expressions. Journal of Mathematical Behavior, 26, 195-210.

Simon, M.A. (1995). Reconstruction mathematics pedagogy from a constructivist perspective. Journal for Research in Mathematics Education, 26, 114-145.

Zandieh, M. & Rasmussen, C. (2008). A case study of defining: creating a new mathematical reality. Manuscript submitted for publication. (with Rasmussen, C. and Larson, C.)

Zimmermann, Karel, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic [MS7, Mon. 12:00, Room 2]

Solving two-sided (max,plus)-linear equation systems

Systems of equations of the following form will be considered:

a_{i}(x) = b_{i}(x) i ∈ I,  (21)

where I = {1, …, m}, J = {1, …, m},

a_{i}(x) = max_{j∈J}(a_{ij} + x_{j}), b_{i}(x) = max_{j∈J}(b_{ij} + x_{j}) ∀i ∈ I

and a_{ij}, b_{ij} are given real numbers. The aim of the contribution is to propose a polynomial method for solving system (21). Let M be the set of all solutions of (21), let M(\overline{x}) denote the set of solutions of system (21) satisfying the additional constraint x ≤ \overline{x}, where \overline{x} is a given fixed element of R^{n}. The proposed method either finds the maximum element of the set M(\overline{x}) (i.e. element x̂ ∈ M(\overline{x}), for which x ∈ M(\overline{x}) implies x ≤ x̂), or finds out that M(\overline{x}) = ∅. The results are based on the following properties of system (21) (to simplify the notations we will assume in the sequel w.l.o.g. that a_{i}(\overline{x}) ≥ b_{i}(\overline{x}) ∀ i ∈ I and \overline{x} ∉ M(\overline{x})):

(i) M(\overline{x}) = ∅ ⇒ M = ∅. (ii) Let K_{i} = \{k ∈ J ; a_{ik} ≤ b_{ik}\} ∀i ∈ I. If for some i_{0} ∈ I the set K_{i_{0}} = ∅, then M(\overline{x}) = ∅. (iii) Let β_{i}(\overline{x}) = max_{k∈K_{i}}(b_{ik} + \overline{x}_{k}), L_{i}(\overline{x}) = \{j ∈ J ; a_{ij} + \overline{x}_{j} > β_{i}(\overline{x})\}, ∀ i ∈ I. If ⋃_{i∈I} L_{i}(\overline{x}) = J, then M(\overline{x}) = ∅. (iv) Let V_{j}(\overline{x}) = \{i ∈ I; j ∈ L_{i}(\overline{x})\}, let \overline{x}_{j}^{(1)} = min_{i∈V_{j}(\overline{x})}(β_{i}(\overline{x}) − a_{ij}) for all j ∈ J, for which V_{j}(\overline{x}) ≠ ∅ and \overline{x}_{j}^{(1)} = \overline{x}_{j} otherwise. Let β_{i}(\overline{x}^{(1)}) < β_{i}(\overline{x}) for all i ∈ I. Then for at least one i ∈ I the value β_{i}(\overline{x}^{(1)}) is equal to at least one of the threshold values b_{ij} + \overline{x}_{j} < β_{i}(\overline{x}).

The method successively determines variables, which have to be decreased if equalities in (21) should be reached. If all variables have to be set in movement, no solution of (21) exists. If the set of unchanged variables is nonempty, the maximum element of (21) is obtained. Using these properties a polynomial behavior of the proposed method can be proved (in case of rational or integer inputs). Possibilities of further generalizations and usage in optimization with constraints (21), as well as applications to synchronization problems will be briefly discussed.

Zúñiga, Juan Carlos, Department of Mathematics, University of Calgary, Calgary, Alberta, Canada [MS6, Tue. 18:10, Room 2]

Matrix polynomials, rational matrices and linear systems: A review

Scalar and matrix functions whose entries are polynomial or rational functions are essential tools of mathematics and its applications, and particularly of systems theory. It can be argued that two schools of thought have emerged, in applied linear algebra and in systems theory, which are concerned with the same problems, but have developed independent literatures. In this note, we review basic ideas which are common to both schools and, thereby, clarify connections and facilitate communication between them. Our interest focuses particularly on the study of eigenvalues, poles, and zeros of polynomial and rational matrix functions as mathematical models of multivariable linear differential (dynamical) systems. It is not our intention to give a deep analysis on differential (dynamical) systems, we focus only in the different ways that matrix polynomials and rational matrices are used to model linear systems. We also argue on the importance of the structural properties of these matrix functions when describing the dynamics of the modeled system. Then we present different methods to obtain these structural properties, and their relations with the methods used in applied linear algebra and matrix theory, in particular, canonical forms and linearizations. Finally a brief discussion on numerical methods to obtain structural properties of matrix functions is presented. (with Lancaster, Peter)

82

Index

Ahn, Eunkyung, 3 Al Zhour, Zeyad, 3 Andjelic, Milica, 3 Arav, Marina, 3 Aricò, Antonio, 4 Bardsley, John, 4 Barrett, Wayne, 4 Barría, José, 5 Baur, Ulrike, 5 Beattie, Christopher, 5 Bella, Tom, 6 Bengochea, Gabriel, 6 Benner, Peter, 6 Berman, Avi, 7 Bini, Dario, 8 Boettcher, Albrecht, 8 Boimond, Jean-Louis, 8 Bourgeois, Gerald, 9 Brualdi, Richard A., 10 Bru, Rafael, 10 Bueno Cachadina, María Isabel, 10 Butkovic, Peter, 10 Carriegos, Miguel, 11 Castro-González, Nieves, 11 Catral, Minerva, 12 Cheng, Wei, 12 Corral, Cristina, 12 Cortés, Vanesa, 12 Costa, Liliana, 13 Cox, Steve, 13 Cravo, Glória, 13 da Cruz, Henrique F., 14 Damm, Tobias, 14 Day, Jane, 15 Deaett, Louis, 15 DeAlba, Luz, 15 Dhillon, Inderjit, 16 Dodig, Marija, 16 Dogan-Dunlap, Hamide, 16 Dolinar, Gregor, 17 Domínguez, María Elena, 17 Dopazo, Esther, 17 Esen, Özlem, 18 Estatico, Claudio, 18 Eubanks, Sherod, 19 Fassbender, Heike, 19, 21 Feng, Lihong, 22 Fernandes, Rosário, 24 Ferrer, Josep, 24 Fonseca, Carlos, 25 Fošner, Ajda, 25 Frank, Martin, 25 Freund, Roland, 25 Furtado, Susana, 26 Furuichi, Shigeru, 26 Gassó, Maria T., 26 Gaubert, Stephane, 27 Gavalec, Martin, 28 Gemignani, Luca, 28 Glebsky, Lev, 29 Goldberger, Assaf, 29 Gouveia, María, 29 Grout, Jason, 29 Grudsky, Sergey, 29 Gugercin, Serkan, 30 Guo, Chun-Hua, 30 Guzmán, José Ramón, 30 Harel, Guershon, 30 Hershkowitz, Danny, 31 Hnětynková, Iveta, 31 Hogben, Leslie, 32 Horn, Roger, 32 Iannazzo, Bruno, 32 Im, Bokhee, 33 Jiang, Er-Xiong, 33 Karow, Michael, 34 Kirkland, Steve, 35 Klasa-Bompoint, Jacqueline, 35 Klein, Andre, 36 Kopparty, Bhaskara Rao, 36 Körtesi, Peter, 37 Kressner, Daniel, 37 Laffey, Thomas, 37 Lancaster, Peter, 38 Lee, Gue Myung, 38 Lee, Hosoo, 38 Leon, Steven, 39 Li, Chi-Kwong, 39 Loiseau, Jean Jacques, 39 Machado, Silvia, 41 Maracci, Mirko, 42 Marovt, Janko, 43 Marques, Maria-da-Graça, 43 Martínez, José-Javier, 43 Martins, Enide, 44 Martin, William, 44 McDonald, Judith, 45 McEneaney, William, 45 M. Dopico, Froilán, 45 Mead, Jodi, 46 Meerbergen, Karl, 46 Meini, Beatrice, 47 Mena, Hermann, 47 Merlet, Glenn, 48 Mikkelson, Rana, 48 Milligan, Thomas, 48 Mitchell, Lon, 48 Moro, Julio, 49 Morris, DeAnne, 49 Moura, Ana, 49 Nagy, James, 51 Narayan, Sivaram, 51 Neumann, Michael, 51 Olesky, Dale, 52 Olshevsky, Vadim, 52 Palma, Alejandro, 53 Parraguez, Marcela, 53 Patricio, Pedro, 53 Peña, Juan Manuel, 54 Peña, Marta, 54 Perdigão, Cecília, 54 Plavka, Jan, 55 Plestenjak, Bor, 55 Ponce, Daniela, 56 Poole, George, 58 Possani, Edgar, 58 Prokip, Volodymyr, 59 Protasov, Vladimir, 59 Pruneda, Rosa E., 59 Pryporova, Olga, 60 Renaut, Rosemary A., 60 Roca, Alicia, 60 Rodríguez, Juan Alberto, 60 Rosenthal, Peter, 61 Rump, Siegfried M., 61 Russo, Maria Rosaria, 61 Rust, Bert W., 62 Salam, Ahmed, 62 Sánchez Perales, Salvador, 62 Satô, Kenzi, 62 Schaeffer, Elisa, 63 Schaffrin, Burkhard, 63 Schneider, Hans, 63 Sebeldin, Anatoly, 64 Seddighin, Morteza, 64 Semrl, Peter, 64 Sendov, Hristo, 64 Sergeev, Sergey, 65 Shader, Bryan, 65 Shahryari, Mohammad, 65 Shaked-Monderer, Naomi, 65 Singer, Ivan, 65 Sinkovic, John, 66 Sivic, Klemen, 66 Šmigoc, Helena, 66 Soares, Graça, 67 Spitkovsky, Ilya, 67 Stefan, Wolfgang, 67 Stosic, Marko, 67 Strong, David, 68 Stuart, Jeffrey, 68 Szyld, Daniel, 68 Tam, Bit-Shun, 69 Tanguay, Denis, 69 Teixeira Matos, Isabel, 71 Trigueros, María, 71 Uchiyama, Mitsuru, 71 Uhlig, Frank, 73 Vallejo, Ernesto, 73 van den Driessche, Pauline, 73 van der Holst, Hein, 74 Vander Meulen, Kevin, 74 Van Dooren, Paul, 74 Vargas, Xaab Nop, 75 Verde-Star, Luis, 75 Vieira, Luis, 75 Weaver, James, 76 Wojciechowski, Piotr, 76 Wrobel, Iwona, 77 Wu, Pei Yuan, 78 Zandieh, Michelle, 78 Zimmermann, Karel, 80 Zúñiga, Juan Carlos, 80