WORMS Brian's Digest: Linear Algebra

1997 volume



SCI.OP-RESEARCH Digest Mon, 14 Dec Volume 5: Issue 50

Date: Fri, 11 Dec 1998 12:37:13 +0100
From: Herbert Jaeger <herbert.jaeger@gmd.de>
Subject: problem: convex cone left invariant by several matrices
Dear colleagues,

studying stochastic processes, I am struggling with the following problem:

given k matrices A_1, ..., A_k of size n x n, when does a pointed convex cone K in R^n exist, such that all A_i leave K invariant, i.e. such that A_i(K) \subset K for i = 1,...,k? The classical reference Berman/Plemmons (Nonnegative Matrices in the Mathematical Sciences) only states a criterium for the case k = 1, i.e. for a single matrix.

Any help or pointer to relevant work would be warmly appreciated!

Greetings from Sankt Augustin,

Herbert Jaeger

---------------------------------------------------------------- Dr. Herbert Jaeger Phone +49-2241-14-2253 German National Research Center Fax +49-2241-14-2384 for Information Technology (GMD) email herbert.jaeger@gmd.de SET.KI Schloss Birlinghoven D-53754 Sankt Augustin, Germany http://www.gmd.de/People/Herbert.Jaeger/ ----------------------------------------------------------------

SCI.OP-RESEARCH Digest Mon, 23 Nov Volume 5: Issue 47

Date: 19 Nov 1998 00:23:16 GMT
From: "Daniele Zani" <daniezan@tin.it>
Subject: THESIS
I'm doing a tesis on ABS methods for solving system of linear equations. I need sample of particolar matrix to test on my computer. thanks to all. If somebody knows something about ABS methods send a message! I'm connected from italy.

bye bye

Date: 19 Nov 1998 11:00:18 GMT
From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: THESIS
look at the book "A Collection of Matrices for Testing Computational Algorithms" by R.T. Gregory and D.L.Karney, Wiley-Interscience 1969 , SBN 471 32669 0

hope this helps

peter

Date: Sun, 22 Nov 1998 19:59:23 GMT
From: ljuillen@easynet.fr (JUILLEN)
Subject: THESIS
spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) wrote:

>In article <01be1352$b90aeea0$LocalHost@default>, > "Daniele Zani" <daniezan@tin.it> writes: >|> I'm doing a tesis on ABS methods for solving system of >|> linear equations. >|> I need sample of particolar matrix to test on my computer. >|> thanks to all. >snip[] >look at the book >"A Collection of Matrices for Testing Computational Algorithms" >by R.T. Gregory and D.L.Karney, Wiley-Interscience 1969 , >SBN 471 32669 0 >hope this helps >peter Date: 19 Nov 1998 03:00:32 -0800
From: kenton@leland.Stanford.EDU (Kenton K. Yee)
Subject: power of a 3x3 matrix
Let M be an upper triangular 3x3 matrix. What is an analytical expression for M^n = the nth power of M? (n = integer)

kenton@stanford.edu

Date: Thu, 19 Nov 1998 09:01:55 -0500
From: edgar@math.ohio-state.edu (G. A. Edgar)
Subject: power of a 3x3 matrix
hints: Do the diagonal case and the strictly upper triangular case (zeros on the diagonal). Then write the general upper triangular matrix as a sum of one of each. Remember that the binomial theorem is a bit different when the terms do not commute.

Gerald A. Edgar edgar@math.ohio-state.edu

Date: 20 Nov 1998 02:14:58 -0500
From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik)
Subject: power of a 3x3 matrix

A "hands-off" approach (Functional Calculus):

Case when the diagonal entries are distinct, say a, b, c:

Calculate the Lagrange interpolation basis at M, that is,

L1 = (M-b*I)*(M-c*I)/((a-b)*(a-c)) L2 = (M-a*I)*(M-c*I)/((b-a)*(b-c)) L3 = (M-a*I)*(M-b*I)/((c-a)*(c-b)) then for every function f defined on the set {a,b,c},

f(M) = f(a)*L1 + f(b)*L2 + f(c)*L3

Note that L1, L2, L3 are upper triangular, too.

Case when two diagonal entries repeat (a) and the third (b) is different from b:

we denote B=(M-a*I)/(b-a), so that the diagonal entries of B are 0, 0, 1 in some order.

Define

C1 = I - B^2, C2 = B - B^2, C3 = B^2 then for every function f which is defined on {0, 1} and has a derivative at 0,

f(B) = f(0)*C1 + f'(0)*C2 + f(1)*C3

You would be interested in f(z)=(a+(b-a)*z)^n (do check it out), so

M^n = a^n * C1 + (b-a)*n*a^(n-1) * C2 + b^n * C3

The case when the diagonal is {a,a,a} can be treated by binomial expansion since M-a*I=N satisfies N^3=0, so

(a*I+N)^n = a^n * I + n*a^(n-1) * N + (1/2)*n*(n-1)*a^(n-2) * N^2

It is in the nature of matrices that a unified formula is hard to come by.

Good luck, ZVK(Slavek).


SCI.OP-RESEARCH Digest Tue, 9 Nov Volume 5: Issue 46

Date: Thu, 12 Nov 1998 10:23:13 +0100 From: Stephane VIALETTE <vialette@liafa.jussieu.fr>
Subject: boolean matrix
Hello,

Just a quick question about boolean matrix decomposition.

Let M be a square boolean matrix. Given M, I am looking for necessarily and sufficient conditions to decide if a decomposition

M = P L Q

exists, where P and Q are permutation matrices (BUT, P is not necessarily the transpose of Q) and L is a lower triangular boolean matrix.

I can find (construct) such a decomposition (of course if such a decomposition exists) but only if L is a stricly lower triangular boolean matrix (no '1' on the diagonal).

If any of you can help me ...

Vialette Stephane vialette@liafa.jussieu.fr LIAFA - Universite Paris VII Place Jussieu 75005 Paris

SCI.OP-RESEARCH Digest Mon, 28 June 98 Volume 5: Issue 26

Date: Wed, 24 Jun 1998 00:00:30 GMT
From: busygin@a-teleport.com
Subject: Please look at this hypothesis
Hello All,

I consider relations between real and boolean solutions of linear algebraic systems of equations, which have a boolean matrix and always 1 in the right part (i.e. Ax=b; a(i,j) \in {0,1}; b(i)=1 for all i). I need to determine cases when the set of real solutions is the convex hull of the set of boolean solutions. I have a hypothesis on a sufficient condition for such relations. In order to formulate it let's introduce a graph by the following rule. The set of vertices of the graph is the set of variables of the system and there is an edge between two vertices if two corresponding variables are included in the same equation. In this case we will say that the edge is induced by the equation. Obviously, one edge can be induced by many equations.

The Hypothesis: If there is no odd cycle in the graph or in every odd cycle there are at least two edges induced by the same equation then the set of real solutions of the system is the convex hull of all boolean solutions of the system.

I believe that the hypothesis is true and I try to prove it for some months. But I am not an expert in convex analysis and algebra. So, if you have an idea about this problem or can suggest me something, please help me. It is very important for my research on universal solving methods for class NP.

Thank you in advance,

Stas Busygin email: busygin@a-teleport.com NP-Completeness Webpage: http://www.busygin.dp.ua/npc.html http://www.geocities.com/SiliconValley/Haven/5779/ Date: 25 Jun 1998 00:47:44 +0200
From: Tuomo Takkula <tuomo@cs.chalmers.se>
Subject: Please look at this hypothesis
Hi.

Your approach sounds remotely familiar. Have a look at the keywords (totally) unimodular matrices, balanced matrices, network matrices in Schrijver, Theory of linear and integer programming, Wiley, 1986.

Best regards

Tuomo

Date: Thu, 25 Jun 1998 23:00:49 GMT
From: busygin@a-teleport.com
Subject: Please look at this hypothesis
These concepts are relevant if the vector in the right part is arbitrary integer (because arbitrariness is used in the proof of necessity of unimodularity). But I consider a particular case when all components of the vector in the right part are 1. So I think unimodularity is not necessary in this case.

P.S. In the previous message I forgot to mention that I mean the set non-negative integer solutions.

Best wishes,

Stas Busygin email: busygin@a-teleport.com NP-Completeness Webpage: http://www.busygin.dp.ua/npc.html http://www.geocities.com/SiliconValley/Haven/5779/ Date: 26 Jun 1998 12:36:19 -0400
From: ladanyi@CS.Cornell.EDU (Laszlo Ladanyi)
Subject: Please look at this hypothesis
The model you describe is called Set Partitioning Problem. There is a base set, its elements correspond to the rows of the matrix. There are subsets, these correspond to the columns (an element of the base set is in the subset if there is a 1 in the matrix at the intersection of the corresponding row and column). The objective is to select (with minimal cost) a disjoint set of subsets so that they cover the base set, i.e., partition the base set.

The graph you describe is called the intersection graph corresponding to the given SPP.

Odd cycles do play an important role in the SPP, they generate valid inequalities, and if they are odd holes (cycles without a chord) then the generated valid inequalities are facet defining.

Try to search for these keywords. Your hypothesis might be true, even though the SPP is NP complete in general. If your hypothesis is true then you have characterized a special case. You can try to look at Lovasz-Plummer: Matching Theory, it has some discussion on the SPP and describes a few special cases.

--Laci

---------------------------------------------------------------------- | Laci Ladanyi | God made one mistake when he created man: | | ladanyi@cs.cornell.edu | He wrote self-modifying code ... | ----------------------------------------------------------------------

SCI.OP-RESEARCH Digest Mon, 8 Jun 98 Volume 5: Issue 23

Date: Tue, 02 Jun 1998 08:53:38 +0200
From: Didier Henrion <henrion@laas.fr>
Subject: Levinson-Szego method for Toeplitz system
Hello,

I'm trying to solve the matrix polynomial equation

A(s)*X(s) = B(s) where A(s) = A0 + A1*s + .. + An*s^n X(s) = X0 + X1*s + .. + Xm*s^m B(s) = B0 + B1*s + .. + Bp*s^p (p = n+m) are polynomial matrices in the indeterminate s.

Upon equating powers of s, I get a Toeplitz linear system of equations


      [ A0          ]
      [ A1 A0       ]
      [ .. A1 ..    ]
      [ An ..    A0 ] [ X0 ]   [ B0 ]
      [    An    A1 ] [ X1 ]   [ B1 ]
      [       .. .. ] [ .. ] = [ .. ].
      [          An ] [ Xm ]   [ Bp ]


My question is: do you know any Levinson-Szego method that
takes advantage of the Toeplitz structure for solving this system ?

Any help, pointer or advice is welcome.

--------------------------------------------------------------- Didier Henrion LAAS-CNRS / Groupe CSC / Bureau E50 7 Avenue du Colonel Roche 31077 Toulouse Cedex 4, France Phone: (33 5) 61 33 69 49 Fax: (33 5) 61 33 69 69 E-mail: henrion@laas.fr WWW: http://www.laas.fr/~henrion --------------------------------------------------------------- Date: Thu, 04 Jun 1998 08:23:53 +0200
From: Didier Henrion <henrion@laas.fr>
Subject: [Q] Solving block Toeplitz system
Hello,

Does anybody know an efficient and reliable method for solving the following block Toeplitz linear system of equations for matrices X0, X1, .., Xm ?


[ A0          ]
[ A1 A0       ]
[ .. A1 ..    ]
[ An ..    A0 ] [ X0 ]   [ B0 ]
[    An    A1 ] [ X1 ]   [ B1 ]
[       .. .. ] [ .. ] = [ .. ].
[          An ] [ Xm ]   [ Bp ]
Thanks for any help.

---------------------------------------------------------------
Didier Henrion

LAAS-CNRS / Groupe CSC / Bureau E50
7 Avenue du Colonel Roche
31077 Toulouse Cedex 4, France

Phone:  (33 5) 61 33 69 49  Fax:    (33 5) 61 33 69 69
E-mail: henrion@laas.fr     WWW:    http://www.laas.fr/~henrion
---------------------------------------------------------------
Date: Sat, 06 Jun 1998 17:55:31 -0400
From: "Scott D. Berger" <sberger@afit.af.mil>
Subject: [Q] Solving block Toeplitz system
To: Didier Henrion <henrion@laas.fr>

Look at the following reference and the references therein:

Cortelazzo, Mian, Rinaldo, 'Toeplitz properties of the block matrices encountered in the processing of spatiotemporal signals,' IEEE Trans. on Signal Processing, Vol 39, No 7, July 1991, pages 1672--1674.

Yagle, 'Multichannel coupled split algorithms for non-Hermitian block-toeplitz matrices,' IEEE Trans. on Signal Processing, Vol 41, No 1, January 1993, pages 505--508.

Bouras, Glentis, Kalouptsidis, 'Architectures for block Toeplitz systems,' Signal Processing, Vol 51, No 3, 1996, pages 167 --

Scott


SCI.OP-RESEARCH Digest Mon, 25 May 98 Volume 5: Issue 21

Date: Tue, 19 May 1998 18:12:29 +0200
From: Didier Henrion <henrion@laas.fr>
Subject: [Q] Volume of an ellipsoid of matrices
Hello,

an ellipsoid of matrices is defined as a set

E = {X : (X-X0)'*P*(X-X0) <= R}

where X is a rectangular matrix and X0, P and R are given matrices.

Does anybody know something about the volume of E ?
Can it be expressed as a function of X0, P and R ?

Any help, advice or pointer is welcome,

Thanks.

---------------------------------------------------------------
Didier Henrion

LAAS-CNRS / Groupe CSC / Bureau E50
7 Avenue du Colonel Roche
31077 Toulouse Cedex 4, France

Phone:  (33 5) 61 33 69 49  Fax:    (33 5) 61 33 69 69
E-mail: henrion@laas.fr     WWW:    http://www.laas.fr/~henrion
---------------------------------------------------------------
Date: Wed, 20 May 1998 16:18:34 GMT
From: Mark Brown <brown.m.w@postal.essd.northgrum.com>
Subject: [Q] Volume of an ellipsoid of matrices
Didier,

If the matrix P is your covariance matrix representing the covariance of a multidimensional distribution, then typically one is interested in computing the (hyper)volume of the n-sigma error ellipsoid. The volume of a hyper-ellipsoid is given by:

V = pi^(m/2) * alpha^m * sqrt(|P|) / gamma(m/2+1)

where

      m is the dimension of P (i.e. P is an mxm matrix)
      alpha is the number of sigma's for the ellipse of interest
      |P| is the determinant of P
      gamma is the gamma function:
           gamma(1) = 1
           gamma(n) = (n-1)!
           gamma(1/2) = sqrt(pi)
           gamma(m/2+1) = m/2*gamma(m/2)
I hope this helps.

-Mark-

Date: Tue, 19 May 1998 20:17:40 GMT
From: bobs@rsa.com
Subject: [Q] Volume of an ellipsoid of matrices
My stupidity must be showing, but I'm not sure I understand the question. You have defined a set of matrices such that each matrix in the set satisfies a certain property. What do you mean by 'volume of E'? The volume of a set of points may be defined as the volume of the minimal convex hull enclosing them. But I don't understand how to define the 'volume' of a set of matrices. Please enlighten me.

If one considers the ellipsoid given by X^t A X <= R, where A is a pos. def. n x n matrix, X is an n-vector and R is real, then the volume of the ellipsoid is easily seen to be just the volume of the n-sphere times the determinant of A, i.e. we have an affine transform of the sphere, so just multiply by the Jacobian of the transform.

Date: 19 May 1998 22:44:14 GMT
From: israel@math.ubc.ca (Robert Israel)
Subject: [Q] Volume of an ellipsoid of matrices
Presumably, consider the m x n real matrices as corresponding to R^(m*n) with Lebesgue measure.

Since Lebesgue measure is invariant under translation, we may assume X0=0. Now if S and T are the positive definite square roots of P and R respectively, you can write

E = {X : ((S X T^(-1))' (S X T^(-1)) <= 1 }

Since the linear transformations X -> S X and X -> X T multiply Lebesgue measure on R^(m*n) by det(S)^n and det(T)^m respectively, the measure of E is det(S)^-n det(T)^(m) = sqrt(det(R)^m/det(P)^n) times the measure of

E1 = {X : X' X <= 1}

which also corresponds to the set of all linear contractions from R^n to R^m.

Unfortunately, I don't know how to compute the measure of E1. It's certainly positive and finite.

>If one considers the ellipsoid given by X^t A X <= R, where A is a pos. >def. n x n matrix, X is an n-vector and R is real, then the volume of the >ellipsoid is easily seen to be just the volume of the n-sphere times the >determinant of A, i.e. we have an affine transform of the sphere, so just >multiply by the Jacobian of the transform.

Not quite: it's sqrt(R^n/det(A)) times the volume of the unit n-sphere.


Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Z2

SCI.OP-RESEARCH Digest Mon, 2 Feb 98 Volume 5: Issue 5

Date: Thu, 22 Jan 1998 18:30:14 -0500
From: "Edward Leibnitz" <ed@sdots.com>
Subject: cholesky factorization ....
I mean the Standard Template Library for C++

Edward Leibnitz ed@sdots.com  http://www.sdots.com

SCI.OP-RESEARCH Digest Mon, 26 Jan 98 Volume 5: Issue 4

Date: Wed, 21 Jan 1998 21:20:35 -0500
From: "Edward Leibnitz" <ed@sdots.com>
Subject: cholesky factorization
Is there any good code "out there" for solving sparse cholesky factorizations using the STL implementation of sparse matrices?

any help?????????

Edward Leibnitz ed@sdots.com http://www.sdots.com

Date: 22 Jan 1998 09:48:41 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: cholesky factorization ....
I don't know what you mean by STL. Sparse Cholesky is possible using the meschach library (from netlib) or UMFPACK (from netlib/linalg)

hope this helps

peter


SCI.OP-RESEARCH Digest Mon, 12 Jan 98 Volume 5: Issue 2

Date: Mon, 12 Jan 1998 21:37:12 +0900
From: Cho Young Cheol <jyc@cisl.snu.ac.kr>
Subject: Help me for determining A' and k' in A'm >= k'

Hi everyone,

I want to know there is any algorithm to solve following problem;

Q. find A' matrix and k' vector satisfying that


    A'm >=k'  <=>(if and only if)  m = Ex;
                                   Ax  >= k;
                                   x >= 0;
where x and m are the vectors of variables, A and E are a matrix of known positive coefficients, and k are vectors of known positive coefficients.

Would you let me know any information such as it's not possible.... or the reference is found in .a book...

Thank you in advance for your advice.

---------------------------------------------------------------------
Young Cheol, Cho                          Ph. D. Student
                                          Phone : 82-2-880-7314
Control Information Systems Lab.          Fax   : 82-2-871-7010
School of Electrical Eng.                 E-mail: jyc@cisl.snu.ac.kr
Seoul Natl. Univ., Seoul 151-742 KOREA    http://cisl.snu.ac.kr/~jyc
---------------------------------------------------------------------

Crawl back to front page.