1 ℤ_{2}-graded symmetry classes of tensors

By M. Shahryari.

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.

2 Matrix Results on Weighted Drazin Inverse and Some Applications

By Zeyad Al Zhour and Adem Kilicman.

In this paper, we present two general representations of the weighted Drazin inverse A_{d,W} of an arbitrary rectangular matrix AM_{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.

3 Stopping rules for a nonnegatively constrained iterative method for ill-posed Poisson imaging problems

By Johnathan M. Bardsley.

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.

4 Euler’s difference table and maximum permanents of (0, 1)-matrices

By Fanja Rakotondrajao.

First, we will enumerate the injections from [m] to [n] without k-fixed-points, that is, injection f without i such that f(i) = i+k. We will deduce the exact values of maximum permanent of (0, 1)−m×n matrices having m−k numbers of zero entries for any non negative integers 0 ≤ k ≤ m ≤ n. Unexpectedly these values are related to the numbers d_{n}^{k} of k-fixed-points-permutations over [n]. The numbers d_{n}^{k} are the derivate of Euler’s difference table.

5 The ratio between the Toeplitz and the unstructured condition number

By S.M. Rump and H. Sekigawa.

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.

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

By Claudio Estatico.

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, postprocessing 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.

7 Dilation of numerical ranges of normal matrices

By Maria Adam and John Maroulas.

Let A be an n × n normal matrix, whose the numerical range NR[A] is a k−polygon, and let v ∈ ℂ^{n}, be a unit vector. If for a unit vector v ∈ ℂ^{n}, the point v^{∗}Av is interior point of NR[A] and P is an n×(k −1) matrix, such that P^{∗}P = I_{k−1} and v⊥ImP, then NR[A] is circumscribed to NR[C], where C = P^{∗}AP. In this paper, we investigate the converse way, showing how we obtain NR[A], from a (k − 1)−polygon, such that the boundary of NR[C] shares the same tangential points with the sides of both polygons.

8 Algebraic Gramians and Model Reduction for Different System Classes

By Tobias Damm.

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.

9 H2 approximation of linear dynamical systems

By P. Van Dooren, K. Gallivan and P.A. Absil.

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_{2}-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.

10 Least Elements of Polyhedral Sets and Nonnegative Generalized Inverses

By Debashisha Mishra and Sivakumar K.C..

A classical result due to Cottle and Veinott gives a characterization of the existence of the least element of a specific polyhedral set defined by a matrix, in terms of nonnegativity of a left-inverse of the matrix. In this talk we present extensions of this result to semi-infinite matrices and characterize nonnegativity of certain classes of generalized inverses.

11 Numerical ranges of nilpotent operators

By Hwa-Long Gau and Pei Yuan Wu.

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.

12 On low rank perturbations of matrices

By Lev Glebsky and Luis Manuel Rivera.

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.

13 Right gw-majorization on M_{n,m}

By A. Armandnejad

Let M_{n,m} be the set of all n × m matrices with entries in 𝔽 , where 𝔽 is the field of real or complex numbers. An n × n matrix R is said to be a g-row stochastic matrix if Re=e, where e = (1, ..., 1)^{t} ∈ 𝔽^{n}. We introduce the right gw-majorization on M_{n,m} which it say that an n × m matrix A is right gw-majorized by an n × m matrix B and denoted by B ≻_{rwg} A, if there exits a g-row stochastic matrix R such that A=BR. In this paper we study some properties of the right gw-majorization and finally all linear operators that strongly preserve the right gw-majorization will become characterized.

14 Controllability of Matrices with Prescribed Blocks

By Glória Cravo.

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.

15 Implicit Jacobi algorithms for the symmetric eigenproblem

By Froilan M. Dopico.

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.

16 Exponential Integrators for Solving Large-Scale Differential Riccati Equations

By Peter Benner and Hermann Mena.

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 semi-discretization. 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.

17 Bounds for matrices on weighted sequence spaces

By D. Foroutannia. abstract Let w = (w_{n}) be a decreasing non-negative sequence and F be a partition of positive integers. If F = (F_{n}), where each F_{n} is a finite interval of positive integers and also for all n, max F_{n} < min F_{n+1}. The block weighted sequence space l_{p}(w, F) is the space of all real sequences x = (x_{n}) with

∥x∥_{p,w,F} = (∑_{n=1}^{∞} w_{n}| < x, F_{n} > |^{p})^{1/p} < ∞,

where < x, F_{n} >= ∑_{i∈F_{n}} x_{i}. In this paper, we consider inequalities of the form ∥Ax∥_{p,w,F} ≤ L∥Bx∥_{q,v,F}, where A and B are matrix operators, x decreasing non-negative sequence and w, v are weights and also F is a block. Moreover, this study is an extension of some works of which are studied before on sequence spaces l_{p}(v) by J. Pecaric, I. Peric and R. Roki in [3].

18 Matrix Optimization in Statistics

By Morteza Seddighin.

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).

19 Reachability of regular switched linear systems

By Miguel V. Carriegos.

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.

20 On trace inequalities for products of matrices

By Shigeru FURUICHI.

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.

21 Manifold of proper elements

By S.V. Djordjevic and S. Snchez Perales.

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}.

22 On Optimal Condition Numbers For Markov Chains

By Michael Neumann and Nung–Sing Sze.

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

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

By Frank Uhlig, Department of Mathematics and Statistics, Auburn University, Auburn, AL 36849–5310, USA; uhligfd@auburn.edu

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 skewhermitean parts of A and the rotation method introduced by C. R. Johnson in the 1970s to compute the boundary of the field of values.

24 Polynomial regression in the Bernstein basis

By Ana Marco, José-Javier Martínez.

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 matri-

ces. 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)

25 The class of Inverse-Positive matrix with chekecboard pattern

By Manuel F. Abad, Maria T. Gassó and Juan R. Torregrosa.

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 Mmatrix. 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 inversepositive 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 chekecboard 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.

26 Toeplitz matrices with Fisher-Hartwig symbols

By Albrecht B¨”ottcher.

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.

27 On Kleene stars and intersection of finitely generated semimodules

By Sergey Sergeev.

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.

28 On the permuted max-algebraic eigenvector problem

By Peter Butkovic.

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.

29 Few pedagogical scenarios in Linear Algebra with Cabri and Maple.

By Jacqueline Klasa-Bompoint.

I nsert your abstract here Abstract FEW PEDAGOGICAL SCENARIOS IN LINEAR ALGEBRA WITH CABRI AND MAPLE. J. Klasa, Collge Dawson, Montral, Canada. jklasa@dawsoncollege.qc.ca With the appearance of very rapidly improving technologies, since the 90s 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 CASs 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 Antons 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 Qubec’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 R2 and R3. 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 concreteThe 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.

30 On Kleene stars and intersection of finitely generated semimodules

By Sergey Sergeev.

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.

31 Nonsingularity of Divisor Tournaments

By Rohan Hemasinha Dept. of Math/Stat, Univ. of West Florida, Pensacola, FL 32514, USA rhemasin@uwf.edu Jeffrey L. Stuart Dept. of Mathematics, Pacific Lutheran Univ. Tacoma, WA 98447, USA jeffrey.stuart@plu.edu James R. Weaver (speaker) Dept. of Math/Stat, Univ. of West Florida, Pensacola, FL 32514, USA jweaver@uwf.edu.

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: 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 2i < jn. No vertex is adjacent to itself. Definition: 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 iOj, t_{ij} = 0 and t_{ji} = 1 if i&#8740; j for 2i < jn. t_{ii} = 0 for i ∈ {2, 3, …, n}.

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

By Bo Kyung Choi and Gue Myung Lee.

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 interiorpoint 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}{ϵ}).

33 The Q-matrix completion problem

By Luz DeAlba, Leslie Hogben, Bhaba Sharma.

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.

34 A Newton Iteration for estimating the regularizing parameter for discrete ill-posed systems

By Rosemary A Renaut and Jodi L. Mead.

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.

35 Group Inverses of Matrices with Path Graphs

By M. Catral, D.D. Olesky and P. van den Driessche.

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.

36 Skills, Concepts and Models in a Linear Algebra Course

By Ana Moura and Pedro A. Santos.

In recent years, there has been a lot of interest in order reduction of largescale 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 finiteprecision 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.

37 Computing the minimum rank of partial 2-trees

By Hein van der Holst.

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.

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

By Luis Vieira.

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 of A^{j}, j ∈ ℕ_{0} where the scalar product •|• is defined by x|y = trace(x · y). In this work ones 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.

39 Model Reduction for unstable Systems based on Hierarchical Matrix Arithmetic

By Baur, Ulrike and Benner, Peter.

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 datasparse 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.

40 Model Order Reduction of Systems with Coupled Parameters

By Peter Benner and Lihong Feng

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 [?]. 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,  (1)

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 (??), 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}

(2)

by direct matrix multiplication and orthogonalize these coefficients to get the matrix V [?]. 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}, …}

(3)

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 (??) 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} + …] (4)

Using (??), we define

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

We see that R_{0}, R_{1}, …, R_{j}, … include all the coefficient matrices in the series expansion (??). 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}}.  (6)

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

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 (??), 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 (??). Based on this, we develop an algorithm which can compute V in (??) 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 (??). Therefore, this improved algorithm is optimal for the parametric system considered in this paper.

References

[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 model-reduction 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).

Mathematics in Industry and Technology, Faculty of Mathematics, Chemnitz University of Technology, D-09107 Chemnitz, Germany; benner@mathematik.tu-chemnitz.de,

lihong.feng@mathematik.tu-chemnitz.de

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¨”ur Innovationen in Industrie und Dienstleistungen) funded by the German Federal Ministry of Education and Science (BMBF).

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

By Heike Faßbender and Peter Benner.

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 [?]. 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 (??). This can be done using the Bartels–Stewart algorithm [?] or an extension to the case E ≠ I [?, ?, ?]. 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 [?], the sign-function method [?], and the alternating direction implicit (ADI) iteration method [?]. 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.

42 From Total Positivity to Positivity: related classes of matrices

By Juan Manuel Pea.

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.

43 Representations for the generalized Drazin inverse of additive perturbations

By N. Castro-González and M.F. Martínez-Serrano Facultad de Informática, Universidad Politécnica de Madrid, Spain.

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.

zzz

44 Singular systems, state feedback problem

By Marija Dodig.

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.

45 Locally linearly dependent operators

By Peter Šemrl.

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.

46 Balancing-Related Model Reduction for Large-Scale Unstable Systems

By Peter Benner.

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) [?] 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}  (9)

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 (??) (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 (??). 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}  (10)

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., [??) 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 (??) 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.  (11)

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},  (12)

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 (??). 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., [?, ?]. 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 (??) by other positive semidefinite matrices that are associated to (??) 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.

47 Some properties of the class sign regular matrices and its subclasses

By V. Cortés and J.M. Peña.

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.

48 Algebraic Gramians and Model Reduction for Different System Classes

By Tobias Damm.

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 boundary control. In the talk we review these generalizations for different classes of systems and discuss computational aspects.

49 Bounds for the Perron root using max eigenvalues

By Ludwig Elsner, P van den Driessche.

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.

50 Eigenvalues of the sum of matrices from unitary similarity orbits

By Chi-Kwong Li, Yiu-Tung poon and Nung-Sing Sze.

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.

51 Minimum Rank Problems: Recent Developments

By Leslie Hogben.

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.

52 Applications of generalized inverses in art.

By D. Huylebrouck.

The Moore-Penrose inverse of a matrix A corresponds to the (unique) matrix solution X of the system AXA=A, XAX=X, (AX)*=AX, (XA)*=XA. S. L. Campbell and C. D. Meyer Jr, wrote a now classical book Generalized Inverses of Linear Transformations (Pitman Publishing Limited, London, 1979), in which they gave an excellent account on the MP-inverse and other generalized inverses as well. They gave many interesting examples, ranging from Gauss historical prediction for finding Ceres to modern electrical engineering problems. The present paper provides new applications related to art studies: a first one about mathematical colour theory, and a second about curve fitting in architectural drawings or paintings. Firstly, in colour theory, a frequent problem is finding the combination of colours approximating a desired colour as closely as possible using a given set of colours. Plaid fabrics are made by a limited number of threads and when a desired tone cannot be formed by a combination, a least squares approach may be mandatory. Some colour theory specialists suggested sensations, such as the observation of colour, should involve logarithmic functions, but using Campbell and Meyers general set-up, this does not give rise to additional difficulties. Of course, the practical use of this theory should still show the benefit of the proposed mathematical tool, but even as stands it already provides a colourful mathematical diversion. In addition, colour theory as taught today in many art schools and as used in numerous printing or computer problems, is in need of a more rigid mathematical approach, for sure. Thus, this example of an application of the theory of general inverses in art may be welcomed. Secondly, we turn to the formerly very popular activity in architectural circles of drawing all kinds of geometric figures on images of artworks and buildings. Until some 20 years ago, triangles, rectangles, pentagons or circles sufficed, but later more general mathematical figures were used as well, especially since fractals became trendy. Recognizing well-known curves and polygons was seen as a part of the interpretation of an architectural edifice or painting. Eventually, certain proportions in the geometric figures were emphasized, among which the golden section surely was the most (in)famous. Diehards continue this tradition, though curve drawing has lost some credit in recent times, in particular due to some exaggerated golden section interpretations. Today, many journals tend to reject geometric readings in architecture, and the reasons to do so are many. For instance, an architect may have had the intention of constructing a certain curve, but for structural, technical or whatever practical reason, the final realization may not confirm that intention. Or else, a certain proportion may have been used in an artwork, consciously or not, but when such a hidden proportion is discovered afterward, even the author of the artwork may disagree on having used it. Consequently, statements about the presence of a certain proportion or about the good fit of a curve in art often are subjective matters, and thus unacceptable for scientific journals. However, a similarity between these geometric studies in architecture and the history of (celestial) mechanics, as explained Generalized Inverses of Linear Transformations, suggests the so-called least squares method, developed in that field, could be applied to examples in art as well. Just as astronomy struggled for centuries to get rid of its astrological past, an objective approach for the described art studies would be most welcome. Of course, it can be opposed the mathematical method presents an overkill with respect to the intended straightforward artistic applications, but nowadays software considerably reduces the computational aspects. The method turns out to be useful indeed: for instance, while a catenary approximates architect Gaudis Paelle Guell better than a parabola, the least squares method shows a catenary or a parabola can be used for the shape of Gaudis Collegio Teresiano with a comparable error. These results were confirmed by Prof. A. Monreal, a Gaudi specialist from the architects hometown, Barcelona. Another amusing example is the profile of a nuclear power plant, which is described in many schoolbooks as an example of a hyperbola, but an ellipse fits even better. Engineers confirmed the hyperbolic shape is modified at the top to reduce wind resistance. Finally, it is shown how proportions in the Mona Lisa can be studied using generalized inverses, but it remains unsure this application will make the present paper as widely read as Dan Browns da Vinci Code.

53 A fundamental paradox in learning algebra

By Denis Tanguay and Claudia Corriveau.

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 (matrise en didactique des mathmatiques, Universit du Qubec Montral ; cf. Corriveau and 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 Qubec 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 uppersecondary 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. and Tanguay, D. (2007). Synthse du Thme 6 : Transition secondaire / post-secondaire et enseignement des mathmatiques dans le postsecondaire. To appear in Actes du Colloque EMF 2006. Universit de Sherbrooke. Corriveau, C. and Tanguay, D. (2007). Formalisme accru du secondaire au collgial : les cours d’Algbre linaire comme indicateurs. To appear in Bulletin AMQ, Vol. XLVII, n4. Dorier, J.-L., Harel, G., Hillel, J., Rogalski, M., Robinet, J., Robert, A. and Sierpinska, A. (1997). Lenseignement de lalgbre linaire en question. J.-L. Dorier, ed. La Pense 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, n3, 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, n2, pp. 139-148. Robert, A. (1998). Outils danalyse des contenus mathmatiques enseigner au lyce et luniversit. Recherches en didactique des mathmatiques, vol. 18, n2, pp. 139-190. Rogalski, M. (1990). Pourquoi un tel chec de l’enseignement de l’algbre linaire ? In Enseigner autrement les mathmatiques en DEUG Premire Anne, Commission inter-IREM universit (ed.), pp. 279-291. IREM de Lyon. Sierpinska, A., Dreyfus, T. and Hillel, J. (1999). Evaluation of a Teaching Design in Linear Algebra : the Case of Linear Transformations. Recherches en didactiques des mathmatiques, Vol. 19, n1, pp. 7-40.

54 NUMBER THEORY

By Habel Mathewkutty .

Polyhedrons are Geometrical shapes enclosed by polygons. Numbers on them can be represented by Habel Math formula Akn = 2k(n-1) + 1 Habelmath sum = Hkm = (m/3)k(m - 1)(2m - 1) + 6 2+ 2(k +1)+ 2(4k + 1)+ 2(9k +1) + 2(16k +1)+.........+ 2(m-1)k + 1=H where H = (m/3)k(m-1)(2m - 1) + 6 Habel Math’s wonderful formula for sum to m terms of all Polyhedral numbers. Remember k = 1 for Tetrahedron, and k=29 for Soccerball because we know the soccerball numbers are A29n = 229(n - 1) + 1 They are 2, 60, 234, 524, ................... So H29m = (m/3)29(m - 1)(2m - 1) + 6 When m=4 it should be 2+60+234+524 = 820 By Prof. Habel Mathewkutty M. Sc.(Math/Agra), Ph. D. Speaker of SIAM conference NW08 in Rome 21-24 July 2008. Former Researcher of Indian Institutes of Technology and Instructor of Houston Community College System.

55 Asymptotic Behavior of Solutions of Stochastic Equations and Applications in Statistical Parameter Estimation

By Hussein Salem Kaibah.

In different models that appear in numerical mathematics , stochastic optimization problems , statistical parameter estimation we come to the necessity to study the behavior of solutions of stochastic equations. Let us consider the following example . Example : suppose that we would like to find a solution of a deterministic equation where is some continuous function, and is some bounded region. But according to the real scheme of calculations we measure the function with random errors in the form : where are jointly independent families of random function (fields) such that . In this case it is reasonable to approximate the function by the averaging Therefore a natural question appears : in what sense and under which condition a solution of a stochastic equation approximates a solution of the first equation as .

56 Shrinkage Estimators for Estimation the Multivariate Normal Mean Vector under Degrees of Distrust

By Ibrahim Hanaish and Abdunnabi M. Ali Elbouzedi.

The estimation of the mean vector of multivariate normal population with special covariance matrix is considered when uncertain non-sample prior information is available. In this paper, four possible estimators are considered, namely, the usual maximum likelihood estimator (UE), the restricted estimator (RE), the preliminary test estimator (PTE) and the shrinkage estimator (SE) under more general setting. The performances of the estimators are compared based on the criteria of unbiasedness and the risk function to a specific quadratic loss function in order to search for best estimator. Both analytical and graphical methods are explored. It is shown that neither PTE nor SE dominates each other, though they fare well compare to UE and RE.

57 Eigen-reduction of Large Scale Neuronal Networks

By Tony Kellems, Derrick Roos, Nan Xiao and Steve Cox.

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.

58 Solving two-sided (max,plus)-linear equation systems.

By Karel Zimmermann.

Systems of equations of the following form will be considered:

a_{i}(x) = b_{i}(x) i ∈ I,  (13)

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 (??). Let M be the set of all solutions of (??), let M(\overline{x}) denote the set of solutions of system (??) 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 (??) (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 (??) should be reached. If all variables have to be set in movement, no solution of (??) exists. If the set of unchanged variables is nonempty, the maximum element of (??) 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 (??), as well as applications to synchronization problems will be briefly discussed.

59 Orderings of matrix algebras and their applications

By Piotr Wojciechowski.

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 [?] that the positivity of I forces a latticeordering 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 [?]. 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 [?]): 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 [?].) 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 [?]. 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 [?].) 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 latticeordered 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

60 Kronecker Products in Imaging Sciences

By James G. Nagy.

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.

61 A Java applet and introductory tutorial for the Jacobi, Gauss-Seidel and SOR Methods

By David Strong.

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.

62 A Truncated Singular Component Method for Ill-Posed Problems

By Bert Rust and Dianne O’Leary.

The truncated singular value decomposition (TSVD) method for solving illposed 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.

63 Acyclic Birkhoff Polytope

By Liliana Costa, C.M. da Fonseca and Enide Andrade Martins.

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.

64 On the spectra of some graphs like weighted rooted trees

By Rosário, Helena Gomes and Enide Andrade Martins.

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.

65 On Steady State Controller in Min-Plus Algebra

By J.-L. Boimond, S. Lahaye.

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.

66 Commutativity preserving maps on real matrices

By Ajda Fošner.

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.

67 Average minimum rank of a graph

By Francesco Barioli, Shaun Fallat, Tracy Hall, Daniel Hershkowitz, Leslie Hogben, Ryan Martin, Bryan Shader, Hein van der Holst.

We establish asymptotic upper and lower bounds on the average minimum rank of a graph using probabilistic, linear algebraic and graph theoretic techniques.

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

By Mirko Maracci.

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.

69 References

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.

70 Your title here

By names of all authors here. A new class of g-inverses and order relations on index 1 matrices (Abstract) In this paper we introduce two new classes of g-inverses of a matrix A of index 1 over an arbitrary eld. We obtain some properties of these generalized inverses and identify the class of all commuting g-inverses as one of the classes of these new classes of g-inverses. The problem of one sided sharp order has been also studied and these new g-inverses have been found very useful in characterizing it. We also give conditions under which one sided sharp order becomes full sharp order. Finally we study the sharp order for partitioned matrices.

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

By Volodymyr Prokip. 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}}) .

72 Reachability cone of eventually exponentially nonnegative matrices

By Dimitrios Noutsos and Michael Tsatsomeros.

We examine the relation between eventual exponential nonnegativity of a matrix A (e^{tA} ≥ 0 for all sufficiently large t ≥ 0) and eventual nonnegativity of I + hA, h ≥ 0 ((I + hA)^{k} ≥ 0 for all sufficiently large k ≥ 0). As a consequence, we are able to characterize initial points x_{0} ∈ ℝ^{n} such that e^{tA}x_{0} becomes and remains nonnegative as exactly those points for which the discrete trajectories x^{(k)} = (I+hA)^{k}x_{0} become and remain nonnegative. This extents work on the reachability cone of exponentially nonnegative matrices by Neumann, Stern and Tsatsomeros [1]. [1] M. Neumann, R.J. Stern, and

M. Tsatsomeros. The reachability cones of essentially nonnegative matrices. Linear and Multilinear Algebra, 28:213–224, 1991.

73 Tensor Sylvester matrices and information matrices of multiple stationary processes

By André Klein, Department of Quantitaive Economics, University of Amsterdam, Roetersstraat 11, 1018 WB Amsterdam, The Netherlands.

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.

74 Max-min convexity

The max-min semifield 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 new 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.

75 Max-min convexity

The max-min semifield 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 new 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.

76 M

S7 Your title here Max-min convexity

The max-min semifield 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 new 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.

77 Your title here

MS7: Max-min convexity By names of all authors here Ivan Singer

The max-min semifield 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.

78 Your title here

MS7: Max-min convexity By names of all authors here Ivan Singer

The max-min semifield 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