Ask Your Question
1

Finding the matrix of a linear affine transformation and its inverse

asked 2018-03-19 11:03:59 -0500

Dalvir gravatar image

updated 2018-03-19 11:45:30 -0500

How do i get the matrix representation of an affine transformation and it's inverse in sage?

I am more so interested in doing this for random affine transformations as i am using them in a multivariate cryptography scheme but for example the following affine transformation over GF(3)

      [1 0 0 2 0 2]     [1]
      [2 2 1 1 2 0]     [1]
      [2 0 0 2 2 2]     [0]
x |-> [2 2 0 1 1 1] x + [1]
      [1 0 2 0 2 0]     [0]
      [0 0 0 2 0 2]     [2]
edit retag flag offensive close merge delete

Comments

Can you provide an example of an affine transformation you are interested in?

slelievre gravatar imageslelievre ( 2018-03-19 11:07:53 -0500 )edit

I have edited my question with an example, any help would be appreciated.

Dalvir gravatar imageDalvir ( 2018-03-19 11:43:47 -0500 )edit

Do you mean like a projective coordinate representation? In that case if you have Mx+b you could make a block matrix out of M and b like block_matrix([[M,b],[0,1]]) or something, and then get that inverse. But I don't know if this is what you mean by the matrix representation of an affine transformation.

kcrisman gravatar imagekcrisman ( 2018-03-19 12:22:25 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
4

answered 2018-03-22 19:09:29 -0500

slelievre gravatar image

An affine transformation t is given by some square matrix a and some vector b, and maps x to a * x + b.

One can represent such a transformation t by an augmented matrix, whose first n columns are those of a and whose last column has the entries of b. We also denote this matrix by t.

Then the n first columns represent the linear part a of the transformation t, and its last column represents the translation part, the vector b.

Since the transformation t maps a vector x to a * x + b, provided a is invertible, with inverse A, then so is t, and its inverse T maps x to A * x - A * b.

Explanation: if y = t(x), then y = a * x + b, so y - b = a * x, and if a is invertible with inverse A, then A * y + A * (-b) = A * a * x, which means x =A * y + A * (-b), so the linear part isA and the translation part isA * (-b)`.

Therefore the matrix for t_inv, also denoted as T, has A as its first n columns and A * (-b) as its last column.

Here is an implementation of a function that returns the inverse of an affine transformation. The function includes a documentation string which summarizes the discussion above, and an example based on the one in your question.

def affine_inverse(t, as_block_matrix=False):
    """
    Return the inverse of this affine transformation

    The affine transformation is given by some `n` by `(n + 1)`
    matrix `t` whose `n` first columns represent the linear
    part `a` of the transformation, and whose last column represents
    the vector `b`, so that the transformation maps a vector `x`
    to `a * x + b`. Provided `a` is invertible, with inverse `A`,
    then so is `t`, and its inverse `T` maps `x` to `A * x - A * b`.

    Optionally, `T` is returned as a block matrix.

    EXAMPLE::

        sage: k = GF(3)
        sage: alist = [
        ....: [1, 0, 0, 2, 0, 2],
        ....: [2, 2, 1, 1, 2, 0],
        ....: [2, 0, 0, 2, 2, 2],
        ....: [2, 2, 0, 1, 1, 1],
        ....: [1, 0, 2, 0, 2, 0],
        ....: [0, 0, 0, 2, 0, 2],
        ....: ]
        sage: blist = (1, 1, 0, 1, 0, 2)
        sage: a = matrix(k, alist)
        sage: n = a.nrows()
        sage: b = matrix(k, n, 1, blist)
        sage: t = a.augment(b)
        sage: affine_inverse(t)
        [1 0 0 0 0 2 1]
        [1 0 2 2 0 2 2]
        [2 0 1 0 2 0 1]
        [2 1 0 2 1 0 1]
        [2 0 2 0 0 2 0]
        [1 2 0 1 2 2 1]
        sage: affine_inverse(t, as_block_matrix=True)
        [1 0 0 0 0 2|1]
        [1 0 2 2 0 2|2]
        [2 0 1 0 2 0|1]
        [2 1 0 2 1 0|1]
        [2 0 2 0 0 2|0]
        [1 2 0 1 2 2|1]
    """
    k = t.base_ring()
    n = t.nrows()
    a = t.delete_columns([n])
    b = t.delete_columns(range(n))
    A = ~a
    if as_block_matrix:
        return block_matrix(k, 1, 2, [A, A * -b])
    return A.augment(A * -b)
edit flag offensive delete link more

Comments

Okay, so it is what I thought. Nice example.

kcrisman gravatar imagekcrisman ( 2018-03-27 20:58:43 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-03-19 11:03:59 -0500

Seen: 240 times

Last updated: Mar 22