larry hammick

"ieee std"

If we're talking only of square matrices, det(A) will have to be equal to
det(B)det(C). Better, the characteristic polynomial of A will be the product
of the c.p.'s of B and C.
But you might want to clarify just what is meant by "factorization". E.g. if
B is invertible (e.g. a 0-1 matrix representing a permutation) then we can
always "factor" A as A=BDB^{-1} simply by setting
D=B^{-1}AB.
LH

hsjameson

(For which 2x2 matrices A can we find 2x2 matrices B, C with positive
integer entries such that A = BC?)

If we simply require the elements of B and C to be positive, not
necessarily positive integers, the problem is simple.

Let A = [ a1 a2 ] for ease of notation
[ a3 a4 ]

If any element of A is nonpositive then it is clearly imposssible for
all entries of B and C to be positive.

On the other hand, if all of the elements a1, a2, a3, a4 of A *are*
positive, we can let B be a positive perturbation of the identity
matrix, guaranteeing that the matrix C is sufficiently close to A that
it is itself positive.

********ly, let B be the perturbed identity matrix

[ 1 d ]
[ d 1 ]

where 0 < d < 1 is strictly less than min(a1/a3, a3/a1, a2/a4, a4/a2),
and let C be the matrix

1/(1 - d^2) * [ a1 - d*a3 a2 - d*a4 ]
[ a3 - d*a1 a4 - d*a2 ]

Now, since 1/(1 - d^2) > 0, all the entries of C are positive from the
definition of d (for instance, we can be certain that a1 - d*a3 > 0
since this is equivalent to d < a1/a3). The form of C can be found
directly by inverting the matrix B and calculating B^(-1)A.

It is simple to confirm that the product BC is equal to the original
matrix A. Moreover, this result may be generalised to higher
dimensions: for instance, given a 3x3 matrix A with positive entries,
choose B to be the matrix

[ 1 d d ]
[ d 1 d ]
[ d d 1 ]

This matrix is certainly invertible for 0 < d < 0.5, and we can find a
suitable d simply by computing C = B^(-1)A as a function of d, and
decreasing d towards zero until C is sufficiently close to A that it
is a positive matrix.

HJ

ieeestd802

Thanks for all reply.
The original post is to seek A= BC where each element of A, B, C
is positive integer.

Is it a simple way to do this ?

dgoncz

If A has no coprime elements? Maybe.

If the elements of A are pairwise coprime? I don't think so.

Can anyone confirm?

Yours,

Doug Goncz, Replikon Research, Seven Corners, VA
Unequal distribution of apoptotic factors regulates
embryonic neuronal stem cell proliferation
Hey, it's a news group! So that's the news!

israel

What, you mean like

[ 5 9 ] [ 1 2 ] [ 1 1 ]
[ 7 11 ] = [ 3 2 ] [ 2 4 ] ?

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2

larry hammick

"Larry Hammick"
....


Oops, sorry, that needs a bit of work. But you get the idea The traces
add, at least.
LH

israel

Maybe not really simple, but it's a finite search.

Let's say

[ a b ] [ s t ] [ w x ]
A = [ c d ], B = [ u v ], C = [ y z ]
Note that a + c = sw + ty + uw + vy = (s+u)w + (t+v)y >= 2 (w+y)
and similarly b + d >= 2 (x + z). So search through all 2 x 2
matrices C of positive integers whose column sums are at most half the
corresponding column sums of A, checking whether A C^(-1) is a matrix
of positive integers, i.e. whether each of az-by, bw-ax, cz-dy, dw-cx
is a positive multiple of det(C).

The search might be cut down significantly.
First note that we may assume det(C) > 0, since if B and C are a solution
then so are BJ and JC where

[ 0 1 ]
J = [ 1 0 ]

Moreover, det(C) must divide det(A).
We want az - by > 0 and c z - d y > 0 so z > max(b/a, d/c) y, and
similarly x < min(b/a, d/c) w.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2

dgoncz

A counterexample to my:


I bow before you, sir. That is to say, I have inspected your counterexample and
found it surprising and correct.

Let's see:

Perhaps it will be true that:

If A is a matrix of unique primes or is pairwise coprime,

and B and C contain no factors of any number in A, and with special
consideration for 1, which is not a prime, but can be a factor, and cannot be
coprime to anything;

Then A # B*C, and we have a new cryptographic method with public key one of A,
B, or C, and private key one of the others?

What is the strength of this method, and how does it increase with rank?

Copy to sci.crypt? I can't do that with aol.

Yours,

Doug Goncz, Replikon Research, Seven Corners, VA
The hormones work at different speeds. In a fight-or-flight scenario,
glucocorticoids are the ones drawing up blueprints for new aircraft carriers;
epinephrine is the one handing out guns.

israel

That posting of mine assumed det(C) <> 0. The case where det(A) = 0
is rather
special and should be dealt with separately. In fact, this case is
easy.

Again I'll write

[ a b ] [ s t ] [ w x ]
A = [ c d ], B = [ u v ], C = [ y z ], A = B C,

where all entries are positive integers, and I'm assuming det(A) = 0.
So det(B) = 0 or det(C) = 0. WLOG assume it's det(C) = 0 (otherwise
do the same ****ysis on A^T = C^T B^T). Then I claim the necessary
and sufficient condition to factor A is gcd(a,b) > 1 and gcd(c,d) > 1.

The columns of C are parallel. Writing w/y = x/z = m/n in lowest
terms, we have [w, y] = e [m, n] and [x, z] = f [m, n] where e,f,m,n
are positive integers. Then [a,c]^T = B [w,y]^T = e B [m,n]^T and
similarly [b,d]^T = f B [m,n]^T. Let [p,q]^T = B [m,n]^T, so p and
q are positive integers with a = p e, c = q e, b = p f, d = q f. Now
[p, q] = m [s, u] + n [t, v]. In particular p >= 2 and q >= 2, so
gcd(a,b) >= 2 and gcd(c,d) >= 2.
Conversely, suppose gcd(a,b) = p > 1 and gcd(c,d) = q > 1. Then
(using the fact that [a,b] and [c,d] are parallel) we can write
[a,b] = p [e,f] and [c,d] = q [e,f]. Then we can
write [p,q] = [1,1] + [p-1,q-1], and we have the factorization

[ 1 p-1 ] [ e f ] [ pe pf ]
[ 1 q-1 ] [ e f ] = [ qe qf ] = A

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2

israel

[3 8] [3 5] [73 127]
[5 8] [8 14] = [79 137]

Note that all entries of A are prime.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2