Sciencemadness Discussion Board - math help

math help

woelen - 14-11-2007 at 05:51

I could help with some math for YT2095, but now I also can use some help with math

.

I need to solve a quadratic equation, in an algebra with multiplication which does not commute, i.e. a*b is not equal to b*a.

The equation to be solved is a simple quadratic one:

x*a*x + b*x + c = 0

Here x is the unknown, a has an inverse a', such that a'*a = a*a' = 1.

How could this be solved? I'm totally stuck.

This of course is a very simple question when for all a and b, a*b = b*a, but when this may not be assumed anymore, then things become totally different. Any clue?

YT2095 - 14-11-2007 at 08:38

Quote:

Originally posted by woelen
in an algebra with multiplication which does not commute, i.e. a*b is not equal to b*a.

How can this be?

unless One of the variables either A or B has a Function as well as a Number attatched to it, or a Priority Function like Brackets with an equation inside.

I`m making no attempt to try and answer this (I think we all Know how crap I am at maths!) I`m asking because I`m Curious too

12AX7 - 14-11-2007 at 10:07

Is there also a division operator?

Non-commuting multiplication is quite common in linear algebra, when multiplying vectors and matrices and such.

[Edited on 11-14-2007 by 12AX7]

woelen - 14-11-2007 at 14:46

Yes, there is a division operator, but a left and a right division.

E.g. if a*b = c, then b = a'*c (provided a has an inverse, i.e. a is not equal to 0).
But if b*a = c, then b = c*a'.

@YT2095: In normal arithmetic as we all learn at school, multiplication always has the property a*b = b*a, for all a and b. But there are many algebra's where this nice property does not hold (sadly). 12AX7 already mentioned an example. My question indeed comes from linear algebra, but not over the field of real numbers, but over a finite field GF(p^n), not to be confused with the ring Z/p^nZ, which is not even a field (the latter has an a and b, such that a and b both are non-zero, while the product a*b equals 0). But that does not matter, the question preferrably should be answered, without referring to some specific algebra.

[Edited on 14-11-07 by woelen]

pantone159 - 14-11-2007 at 20:06

Not sure how helpful this is, but my thoughts so far...

You want to solve: xax + bx + c = 0, which would be the normal quadratic equation if things commuted.
I assume that addition commutes, so a+b = b+a, and normal constant multiplication also commutes, so 2ab = a2b = ab2.
Is that true?

Approaching this like a normal quadratic:

Step 1 - Move c over
xax + bx = -c

Step 2 - Premultiply by 4a
4axax + 4abx = -4ac

Step 3 - Add b*b
4axax + 4abx + b*b = b*b - 4ac

Now, if this were with normal numbers, then the left hand side is equal to:
LHS = (2ax + b)^2
which would then give you:
(2ax + b)^2 = b*b - 4ac
which you solve for x to get the usual quadratic equation.

But, in your case,
(2ax + b)*(2ax + b) =
(2ax)(2ax) + (2ax)(b) + (b)(2ax) + (b)(b) =
4axax + 2axb + 2bax + b*b

This compares to the left side of Step 3:
4axax + 4abx + b*b (LHS 3)
4axax + 2axb + 2bax + b*b (yours)

These are equal if:
2abx = axb + bax

Does that happen to be the case for you? If so, then the usual formula would work.
Otherwise, I'm not sure.

woelen - 14-11-2007 at 23:51

Pantone, thanks for your help, but the last point is exactly where I get stuck. I cannot assume that a*x*b = b*a*x and so, the entire mechanism for solving the equation breaks down

. What you give is a derivation of the well-known formula for solving quadratic equations, such as this is done at high school.

I've done quite some algebraic fiddling around, and I also searched on the Internet, but no success till now. Most likely this kind of equations has a special name. If one knows that name, then that could be helpful also, because searching would be facilitated.

pantone159 - 15-11-2007 at 07:47

Any chance of that last bit being off by a constant?
I.e., 2abx = axb + bax + D, for some constant D.
If that were true, you'd win as well.

Maybe you could solve it iteratively?
E.g., Newton's method, for normal numbers at least, is
x1 = x0 - f(x0) / f'(x0), where f' is the derivative.
For your f(x) = xax + bx + c, f'(x) = ax + xa + b.
I'm not sure if the arithmetic has to be adjusted for your stuff.

Geomancer - 15-11-2007 at 08:39

If you're working with a division algebra over a finite field, it must be infinite dimensional, no? I can't say I've ever worked with these guys, let alone seen a solution for the problem. I can construct simple examples, but perhaps you could fill us in on how you came by this creature, and exactly what it looks like?

woelen - 15-11-2007 at 13:43

This is a problem from cryptography. Right now, I cannot go into very strong detail, but it has to do with computing quadratic residues, but not for numbers, but for square matrices. The problem of computing quadratic residues is a big one on its own, but when done modulo a prime things are much less demanding.

So, the elements a,b,c and x are matrices with elements of a finite field (GF(p^n)). These are discrete fields of characteristic p, and hence, using Newton-like methods are no option over here.

Finally, after searching with quite some effort, I found some material about this subject, but it does not look promising:

https://kb.osu.edu/dspace/bitstream/1811/22234/1/V074N5_273

Apparently, the general solution of this type of equations is not (yet) solved, although I must admin that the info in that paper is more than 30 years old, so things may have changed, but not something I know of. So, I hit something very difficult. I am really amazed that this seemingly simple problem is not yet solved.

So, I am not surprised if you cannot come up with a solution. Probably, I have to dive into the crypto-stuff again and change direction of (re)search.

Geomancer - 15-11-2007 at 19:27

Quote:

Originally posted by woelen
Yes, there is a division operator, but a left and a right division.

E.g. if a*b = c, then b = a'*c (provided a has an inverse, i.e. a is not equal to 0).
[Edited on 14-11-07 by woelen]

I see. That was the bit that confused me. I assume you mistyped, since nonzero matrices are not, in general, invertible.

Note that your problem, as I understand it, is not exactly analogous to the classical one. You seem to be interested in determining the existence of a solution within the base algebra, whereas the classical problem involves constructing a field that contains all solutions.

chemrox - 15-11-2007 at 22:57

Question: Is this a matrix algebra or some other linear calculus?

DerAlte - 31-1-2008 at 11:23

Woelen - I came across this which you posted some time ago and I obviously missed. It intrigued me and I looked into it. You wrote:

Quote:

I need to solve a quadratic equation, in an algebra with multiplication which does not commute, i.e. a*b is not equal to b*a. The equation to be solved is a simple quadratic one:

x*a*x + b*x + c = 0

Here x is the unknown, a has an inverse a', such that a'*a = a*a' = 1.

How could this be solved? I'm totally stuck….

……Yes, there is a division operator, but a left and a right division. E.g. if a*b = c, then b = a'*c (provided a has an inverse, i.e. a is not equal to 0).
But if b*a = c, then b = c*a'….

….but over a finite field GF(p^n), not to be confused with the ring Z/p^nZ, which is not even a field (the latter has an a and b, such that a and b both are non-zero, while the product a*b equals 0). But that does not matter, the question preferrably should be answered, without referring to some specific algebra…. – (italics mine)

…So, the elements a,b,c and x are matrices with elements of a finite field (GF(p^n)). These are discrete fields of characteristic p

Are you still interested in this or have you found a solution? I can solve it, I think, for certain conditions, but I have to re-interpret your equation to make sense of it in a matrix fashion. In particular, I re-write it as:

x’*a*x + b’*x + c = 0; else I cannot interpret it.

I have written up a solution but cannot write it in this very limited font available on the forum. It is a few pages long, in WORD DOC format. I will post it via ftp if you are still interested. I am still wrestling over its validity in GF(p^n) – my abstract algebra is a bit sketchy after 20 years of disuse! I used to use linear algebra in all sorts of applications from circuit theory to pattern recognition, but only touched lightly on abstract during the period I was interested in coding for error correction and crypto. It intrigues me but the excessive terminology is daunting….

Regards,

Der Alte

woelen - 1-2-2008 at 00:19

Der Alte, I certainly am interested in the solution of your reformulated problem. With a' you mean the transpose of a matrix, or do you mean the conjugate transpose of a matrix? For real matrixes this point is moot, but for complex matrixes it does matter.

sparkgap - 1-2-2008 at 02:11

You might want to look up the "quadratic eigenvalue problem" and "matrix solvent" if it's going to branch into linear algebra.

sparky (~_~)

microcosmicus - 1-2-2008 at 12:37

Since you state that a is invertible, we can make a preliminary
simplification. Letting a' denote the inverse of a and defining
y = ax, your equation becomes

a'*y*y + b*a'*y + c = 0 .

We can multiply through by a and define B = a*b*a' and
C = a*c to then obtain the equation

y*y + B*y + C = 0 .

In other words, it is at least possible to eliminate a from consideration.

Unfortunately , this is about all one can do at this level of generality ---
your request "the question preferrably should be answered, without
referring to some specific algebra." doesn't look like it can be fulfilled in
full generality because there are too many non-commutative algebras which
behave in all sorts of ways. By using generators and relations, one can cook
up an algebra in which your equation has pretty much any type of solutions.
If we take a free algebra, the equation x*x + b*x + c = 0
obviously has no solutions because a solution would be a relation
but, by definition, free algebras have no relations. If we take an
algebra with generators a,b,c and the relation a*a*+b*a+c=0.
Likewise, we could concoct algebras in which the equation has any
number of solutions, finite or infinite or in which solutions happen to
equal a specified expression in b and c or no such expression.

Therefore, to make progress, it seems we need to narrow the class of
algebras under consideration. Especially since that is where your question
arose, the class of matrix algebras whose coefficients lie in a field is a
good choice. To stay general, I will not specify the field, but do things
which would be valid for all fields.

To begin, we can at least do something like completing the square to at
least eliminate the trace of b, if not all of b. Set x = y -
(1/4) (tr b) I. (Here, I is the identity matrix.) Then, upon expanding,
we obtain the following equation:

y*y + (b - (1/2) (tr b) I)*y + c - (1/4) (tr b) b + (1/16) (tr b)^2 I = 0

Thus, without loss of generality, we may assume that the trace of b
is zero.

A key observation is that the form of our equation is invariiant under
conjugation. Suppose we set x = m*y*m', where m is
a matrix with inverse m'. Then we see that

y*y + (m'*b*m)*y + m'*c*m = 0 .

Thus, the number and nature of the solutions is invariant under conjugation
and it makes sense to make use of this fact to simplify the problem. One
way is to put the matrices into a canonical form. If the field is algebraically
complete, then one can put one of the matrices, say b, into Jordan
normal form and simplify the other matrix some. However, since this is
not the case for the fields which interest you, I will not carry this idea
further now.

Another idea is to make use of invariants and covariants. The traces
of products of matrices are invariant under conjugation; by the
Cayley-Hamilton theorem, one can express all such quantities in
terms of a finite number of them. Then one could classify the solutions
of your equation for matrices of a certain degree by what these
invariants are doing. Likewise, one could express the solutions
on a covariant form. For the fun of it, I am doing this in the 2x2 case;
since it is quite tedious to write math in this forum, I will stop here
and soon post s TeX document with this analysis of the 2x2 case.
BTW, DerAlte, could you also post what you did, or send me a copy?

[Edited on 1-2-2008 by microcosmicus]

DerAlte - 1-2-2008 at 17:22

For what it's worth, folks:

http://www.sciencemadness.org/scipics/Solve xT.doc

Purely formal solution. Was going to add a bit but ran out of steam: comments and criticism invited! I have not given any serous thought to validity in other than field R.

@Woelen: A' is the normal transpose. I assumed X was real and not complex or Hermitian.

Regards,

DerAlte

[Edited on 1-2-2008 by DerAlte]

woelen - 3-2-2008 at 11:19

If I read the article, then I see that you are not actually solving the equation you mention (it cannot, because it has N unknowns, while there only is one equation), but you reduce it to a purely quadratic form.

I think that this method can be used to transform N equations of the form x'Ax + b'x + c = 0 to N purely quadratic equations, allowing these N equations to be solved as a linear system in N purely quadratic forms. I'll have to go deeper into this matter. Der Alte, your article gives some nice ideas to me and if I find something interesting based on that, I'll come back on that.

Geomancer - 4-2-2008 at 08:42

A summary of DerAlte's method for those so inclined:
The equation xtAx+btx+C=0 can be written as < x, x>+< b',x>+c=0 where <,> is a symmetric bilinear function. This equation can be reduced to the form < y,y>=k by a method entirely analogous to that used to solve the quadratic equation. Note that this holds for all fields of characteristic other than 2. (For characteristic 2 the form <,> might not exist, and completing the square also fails). < y,y>=k is equivalent to the system sum(axi2=k where ai are either +/- 1 or non-quadratic residues (look up "diagonalization of quadratic forms" for more information).

Nice math, but I'm not sure it helps with the original problem. My approach would be to try and find the invariant subspaces of the solution (X, considered as an operator on a vector space). Microcosmicus conveniently reduces the problem to X2+BX+C=0. Using this form of the problem, note that if a space I is X invariant (i.e. XI=I), then BI+I=CI+I. A variant of the Microcosmicus trace elimination technique may allow one to find the spaces I from B and C. This should be enough to solve over an algebraicly complete field. For finite fields, then, one could extend the field to a completion, solve, and discard the solutions that aren't in the original. That's all I have; I actually should be working on other things, but if a solution pops into my head uninvited I'll post it.

DerAlte - 4-2-2008 at 19:08

@Woelen - absolutely. I am having a look at the case where X is also an nxn matrix. There you have N^2 equations and N^2 unknowns and, in principle there is a solution. But it's damned complex....

@Geomancer and Microcosmicos - interesting posts, I need more time to digest. The old brain has slowed down a bit these days.

I intend to repost the Solve xT.doc screed with a few additions soon, when I've sorted some ideas out.

Regards,
Der Alte

DerAlte - 6-2-2008 at 13:57

A bit added at the end (titled addendum), a stab at the NxN case for X. The rest unaltered.

http://www.sciencemadness.org/scipics/Solve_xT.doc

Der Alte