1
$\begingroup$

For $\epsilon > 0$, let $M_{\epsilon}$ be the family of $n$ x $n$ real matrices A such that $||$A$ - $I$_n|| < \epsilon$, where $|| \cdot ||$ is the standard operator norm. If $\epsilon$ is chosen sufficiently small, then all finite products of members of $M_{\epsilon}$ have positive determinant (i.e., they are orientation-preserving). Is this the only requirement for an $n$ x $n$ matrix to be expressible as such a product? If so, that would imply the result that any non-singular $n$ x $n$ matrix can be expressed as a product of $n$ x $n$ matrices that each change only one coordinate (as this is clearly the case for any matrix in $M_{\epsilon}$), which is what I'm trying to prove.

$\endgroup$
2
$\begingroup$

Let $A \in \mathbb{R}^{n \times n}$

Now if $\|A- I_{n} \| < \epsilon $ then I can express $A$ as product of two nearly orthogonal matrices. Right.

An orthogonal matrix is $QQ^{T} = Q^{T}Q = I_{n} $ now...each column of $Q$ is unit normal. So if we build an orthogonal matrix and alter slightly we manipulate the bounds on $\epsilon$ Like the following..

n= 3;
A = rand(n,n);
[Q,R] =qr(A);
I  = eye(n);
err = norm(Q*Q' - I);

now this is zero...for instance...

epsilon = 5;

Q1 = epsilon*Q(:,3);
Q1 = [Q(:,1),Q(:,2),Q1];
err1 = norm(Q1*Q1' -I)

err1 =

   24.0000

From the matrix norms it slightly less than 25...like I expected. This comes from the matrix norm equality

$$ \|AB \| \leq \|A\| \|B\|$$

and $$ \| c A\| \leq |c| \| A \|$$

illustrating that this bounds it closer change epsilon to $1$

n= 3;
A = rand(n,n);
[Q,R] =qr(A);
I  = eye(n);
err = norm(Q*Q' - I);

epsilon = 1;

Q1 = epsilon*Q(:,3);
Q1 = [Q(:,1),Q(:,2),Q1];
err1 = norm(Q1*Q1' -I);

err1 =

   5.1650e-16


Q1 = epsilon*Q(3,3);
Q2 = Q;
Q2(3,3) = Q1;
err1 = norm(Q2*Q2' - I)

Note that since 1 doesn't modify anything it will be close to machine precision or our $\epsilon$

In retrospect that was kind of dumb. We're going to create a matrix from the outer product of two other and subtract it from $I_{n}$

$$A =I_{n} - vu^{t} $$

let $vu^{T}_{ij} = 0 , vu^{T}_{i=j=1} = \epsilon , $

So you have a zero matrix we create we subtract off epsilon from the identity.

$$ \| A - I_{n} \| = \epsilon $$

$$ \| I_{n} - vu^{t} -I_{n} \| = \| vu^{T} \| = \epsilon $$

we can demonstrate this like the following..

n=3;
I =eye(n);
Z = zeros(n);
epsilon = 1e-3;
Z(1,1) = epsilon;
A = I-Z;

error = norm(A-I);

error =

    0.0010

So you simply create an $\epsilon$ and make it smaller.

$\endgroup$
  • $\begingroup$ I'm afraid I don't see how I could use this to answer my question. If an orientation-preserving matrix A is really far away from the identity, how does its QR decomposition help me get it as a product of matrices close to the identity? $\endgroup$ – Davey Aug 6 '18 at 18:01
  • $\begingroup$ I don't understand your concern. The QR decomposition is gram schmidt. I produced a matrix $Q$ which is orthogonal. I've demonstrated that with both code and math. Also there are two parts..one where I create a diagonal matrix like you state because what you're saying is confused. If you subtract $\epsilon $ from identity in the first spot then subtract that from $I_{n}$ you get $\epsilon$ for the norm. $\endgroup$ – Shogun Aug 7 '18 at 0:01
  • $\begingroup$ your constraint is to make something called $\epsilon$ typically people it is very close it can be any number. further more determinant of orthogonal matrices is 1. $\endgroup$ – Shogun Aug 7 '18 at 0:15
0
$\begingroup$

I got the following solution from my algebra professor:

If $H$ is the group of $n \times n$ real matrices with positive determinant, we have that $H$ forms a connected set in the standard topology on $\mathbb{R}^{n^2}$. This is complicated to prove, but it essentially involves showing that any matrix in $H$ can continuously be moved to the identity by adding multiples of some rows to other rows and scaling rows by positive constants (most easily by induction on $n$). So given any matrix $A$ in $H$, there's a path $C$ in $H$ from $I$ to $A$.

We then fix a small $\epsilon > 0$ and let $V$ be the ball around $I$ in $H$ of radius $\epsilon$. We can choose a smaller open ball $U$ around $I$ such that for any matrices $X, Y \in U$, $XY^{-1} \in V$, that is, the multiplicative distance between any two matrices in $U$ is in $V$.

We then note that every matrix $X$ along $C$ yields a multiplicative translate $XU$ of $U$ that is still an open set (because $X$ is just a change of coordinates), and by compactness finitely many of these will cover $C$, so we have a chain $U_1, ..., U_k$ of open sets along $C$ linking $I$ to $A$, such that, by openness and the connectedness of the path, each $U_i$ overlaps with $U_{i+1}$. We can thus take a chain of points (matrices) $X_1, ..., X_{k+1}$ where $X_1 = I$, $X_{k+1} = A$, and for $2 \leq i \leq k$, $X_i \in U_{i-1} \cap U_{i}$. For each $i$, we have that $X_{i+1}^{-1}X_i \in V$, by the definition of $U$, so we can move from $I$ to $A$ via a product of $k$ matrices in $V$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.