Larry hammick2012-05-04 20:11:06

”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

Hsjameson2012-05-05 15:23:11

(For which 2×2 matrices A can we find 2×2 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.

Explicitly, 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

Ieeestd8022012-05-06 15:02:31

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 ?

Dgoncz2012-05-08 05:40:28

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!

Israel2012-05-17 05:25:12

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 hammick2012-05-17 05:25:22

”Larry Hammick”

….

Oops, sorry, that needs a bit of work. But you get the idea ðŸ™‚ The traces

add, at least.

LH

Israel2012-05-17 05:25:31

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

Dgoncz2012-05-18 01:45:37

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.

Israel2012-05-18 21:39:16

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

Robert Israel israel@math.ubc.ca

Department of Mathematics http://www.math.ubc.ca/~israel

University of British Columbia

Vancouver, BC, Canada V6T 1Z2

Israel2012-05-18 21:39:28

[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

Dgoncz2012-05-20 12:58:02

I found this indexing scheme in ACM. It uses factorization of a matrix. Perhaps

the author gives the factoring method.

“In this paper, we propose a novel document clustering method based on the

non-negative factorization of the term-document matrix of the given document

corpus.”

These are large matrices. Are large matrices of interest?

It is in the:

Annual ACM Conference on Research and Development in Information Retrieval

Proceedings of the 26th annual international ACM SIGIR conference on Research

and development in informaion retrieval

Toronto, Canada

SESSION: Clustering

Pages: 267 – 273

Year of Publication: 2003

ISBN:1-58113-646-3

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.

Ieeestd8022012-05-21 10:07:30

Thanks for your reply. However, in above, we can not guarantee that each

element of B, or DB^(-1) are positive integer.

## Leave a Reply

You must be logged in to post a comment.