Linear algebra question relevant to TOP

I can represent an affine subspace of R^n by an ordered pair of a (usually non-square) matrix A and a vector b. The pair (A, b) represents the set of all points x such that A x = b, which is an affine subspace.

Now, given two such pairs, (A1, b1) and (A2, b2), how can I get a matrix and vector pair representing the affine hull of these two affine subspaces?

The method needs either to work with integer arithmetic, or to otherwise resolve the numerical stability issues that come up when two subspaces are *almost* part of the same larger subspace.

I'm sure I can figure this out myself after a while, but I wonder if anyone already knows.

Keenan

On Thu, Jan 26, 2012 at 3:15 PM, Keenan Pepper <keenanpepper@gmail.com> wrote:
>
> The method needs either to work with integer arithmetic, or to otherwise resolve the numerical stability issues that come up when two subspaces are *almost* part of the same larger subspace.

Do you know how to compute the null space of a matrix in a way that
meets your criteria?

-Mike

Keenan's internet seems to have died on XA chat, so I'll repost my
algorithm here. Assume that you have two affine subspaces, Ax = b and
A'x' = b', and you want to find the affine hull for both of them:

1) compute the null space of A
2) compute the null space of A'
3) pick arbitrary solutions x and x' so that the vector (x - x') isn't
the null space of either A or A'
4) compute the matrix such that null(A), null(A'),and x - x' are all
in its null space, call it H
5) Hv = Hx is the matrix you want

My thinking is that if you have equations like

[1 1 0;0 1 4][a;b;c] = [0;1]
[1 0 2;0 5 1][a;b;c] = [0;1]

The first one will characterize the affine subspace which is [-1;1;0]
+ k*[-4;4;1], and the second one will characterize the affine subspace
which is [-2;0;1] + k*[-10;-1;5] for k in R. In regular temperament
terms, you have 3/2 * k*81/80 and 5/4 * k*3125/3072. To find the
affine hull encapsulating both, you need to temper out both 81/80 AND
3125/3027, and you also need to temper out the difference between 3/2
and 5/4, such that they're both possible solutions to the equation Ax
= b for A = the combined affine hull you want. In this case, you end
up tempering out 81/80, 3125/3072, and 6/5, so the matrix in R3 you
want is the zero matrix, meaning that any column vector in R^3 is a
solution: the affine hull of these two skew lines is all of R^3.

-Mike

On Thu, Jan 26, 2012 at 10:26 PM, Mike Battaglia <battaglia01@gmail.com> wrote:
> On Thu, Jan 26, 2012 at 3:15 PM, Keenan Pepper <keenanpepper@gmail.com> wrote:
>>
>> The method needs either to work with integer arithmetic, or to otherwise resolve the numerical stability issues that come up when two subspaces are *almost* part of the same larger subspace.
>
> Do you know how to compute the null space of a matrix in a way that
> meets your criteria?
>
> -Mike