Transpose Algorithm
   HOME

TheInfoList



OR:

In
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices ...
, the transpose of a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations). The transpose of a matrix was introduced in 1858 by the British mathematician Arthur Cayley. In the case of a
logical matrix A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. Matrix representation ...
representing a binary relation R, the transpose corresponds to the
converse relation In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent&n ...
RT.


Transpose of a matrix


Definition

The transpose of a matrix , denoted by , , , A^, , , or , may be constructed by any one of the following methods: # Reflect over its
main diagonal In linear algebra, the main diagonal (sometimes principal diagonal, primary diagonal, leading diagonal, major diagonal, or good diagonal) of a matrix A is the list of entries a_ where i = j. All off-diagonal elements are zero in a diagonal matri ...
(which runs from top-left to bottom-right) to obtain #Write the rows of as the columns of #Write the columns of as the rows of Formally, the -th row, -th column element of is the -th row, -th column element of : :\left mathbf^\operatorname\right = \left mathbf\right. If is an matrix, then is an matrix. In the case of square matrices, may also denote the th power of the matrix . For avoiding a possible confusion, many authors use left upperscripts, that is, they denote the transpose as . An advantage of this notation is that no parentheses are needed when exponents are involved: as , notation is not ambiguous. In this article this confusion is avoided by never using the symbol as a
variable Variable may refer to: * Variable (computer science), a symbolic name associated with a value and whose associated value may be changed * Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
name.


Matrix definitions involving transposition

A square matrix whose transpose is equal to itself is called a ''
symmetric matrix In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally, Because equal matrices have equal dimensions, only square matrices can be symmetric. The entries of a symmetric matrix are symmetric with ...
''; that is, is symmetric if :\mathbf^ = \mathbf. A square matrix whose transpose is equal to its negative is called a ''
skew-symmetric matrix In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition In terms of the entries of the matrix, if ...
''; that is, is skew-symmetric if :\mathbf^ = -\mathbf. A square
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
matrix whose transpose is equal to the matrix with every entry replaced by its
complex conjugate In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, (if a and b are real, then) the complex conjugate of a + bi is equal to a - ...
(denoted here with an overline) is called a ''
Hermitian matrix In mathematics, a Hermitian matrix (or self-adjoint matrix) is a complex square matrix that is equal to its own conjugate transpose—that is, the element in the -th row and -th column is equal to the complex conjugate of the element in the -t ...
'' (equivalent to the matrix being equal to its
conjugate transpose In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex c ...
); that is, is Hermitian if :\mathbf^ = \overline. A square
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
matrix whose transpose is equal to the negation of its complex conjugate is called a ''
skew-Hermitian matrix __NOTOC__ In linear algebra, a square matrix with complex entries is said to be skew-Hermitian or anti-Hermitian if its conjugate transpose is the negative of the original matrix. That is, the matrix A is skew-Hermitian if it satisfies the relatio ...
''; that is, is skew-Hermitian if :\mathbf^ = -\overline. A square matrix whose transpose is equal to its inverse is called an ''
orthogonal matrix In linear algebra, an orthogonal matrix, or orthonormal matrix, is a real square matrix whose columns and rows are orthonormal vectors. One way to express this is Q^\mathrm Q = Q Q^\mathrm = I, where is the transpose of and is the identity m ...
''; that is, is orthogonal if :\mathbf^ = \mathbf^. A square complex matrix whose transpose is equal to its conjugate inverse is called a ''
unitary matrix In linear algebra, a complex square matrix is unitary if its conjugate transpose is also its inverse, that is, if U^* U = UU^* = UU^ = I, where is the identity matrix. In physics, especially in quantum mechanics, the conjugate transpose is ...
''; that is, is unitary if :\mathbf^ = \overline.


Examples

*\begin 1 & 2 \end^ = \, \begin 1 \\ 2 \end * \begin 1 & 2 \\ 3 & 4 \end^ = \begin 1 & 3 \\ 2 & 4 \end * \begin 1 & 2 \\ 3 & 4 \\ 5 & 6 \end^ = \begin 1 & 3 & 5\\ 2 & 4 & 6 \end


Properties

Let and be matrices and be a
scalar Scalar may refer to: *Scalar (mathematics), an element of a field, which is used to define a vector space, usually the field of real numbers * Scalar (physics), a physical quantity that can be described by a single element of a number field such ...
.


Products

If is an matrix and is its transpose, then the result of
matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
with these two matrices gives two square matrices: is and is . Furthermore, these products are
symmetric matrices In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally, Because equal matrices have equal dimensions, only square matrices can be symmetric. The entries of a symmetric matrix are symmetric with re ...
. Indeed, the matrix product has entries that are the
inner product In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often ...
of a row of with a column of . But the columns of are the rows of , so the entry corresponds to the inner product of two rows of . If is the entry of the product, it is obtained from rows and in . The entry is also obtained from these rows, thus , and the product matrix () is symmetric. Similarly, the product is a symmetric matrix. A quick proof of the symmetry of results from the fact that it is its own transpose: :\left(\mathbf \mathbf^\operatorname\right)^\operatorname = \left(\mathbf^\operatorname\right)^\operatorname \mathbf^\operatorname= \mathbf \mathbf^\operatorname .


Implementation of matrix transposition on computers

On a computer, one can often avoid explicitly transposing a matrix in
memory Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered ...
by simply accessing the same data in a different order. For example,
software libraries In computer science, a library is a collection of non-volatile resources used by computer programs, often for software development. These may include configuration data, documentation, help data, message templates, pre-written code and subro ...
for
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices ...
, such as
BLAS Basic Linear Algebra Subprograms (BLAS) is a specification that prescribes a set of low-level routines for performing common linear algebra operations such as vector addition, scalar multiplication, dot products, linear combinations, and matrix ...
, typically provide options to specify that certain matrices are to be interpreted in transposed order to avoid the necessity of data movement. However, there remain a number of circumstances in which it is necessary or desirable to physically reorder a matrix in memory to its transposed ordering. For example, with a matrix stored in row-major order, the rows of the matrix are contiguous in memory and the columns are discontiguous. If repeated operations need to be performed on the columns, for example in a fast Fourier transform algorithm, transposing the matrix in memory (to make the columns contiguous) may improve performance by increasing
memory locality In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference localit ...
. Ideally, one might hope to transpose a matrix with minimal additional storage. This leads to the problem of transposing an ''n'' × ''m'' matrix
in-place In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output ...
, with
O(1) Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...
additional storage or at most storage much less than ''mn''. For ''n'' ≠ ''m'', this involves a complicated permutation of the data elements that is non-trivial to implement in-place. Therefore, efficient
in-place matrix transposition In-place matrix transposition, also called in-situ matrix transposition, is the problem of transposing an ''N''×''M'' matrix in-place in computer memory, ideally with ''O''(1) (bounded) additional storage, or at most with additional storage much ...
has been the subject of numerous research publications in
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, starting in the late 1950s, and several algorithms have been developed.


Transposes of linear maps and bilinear forms

As the main use of matrices is to represent linear maps between
finite-dimensional vector space In mathematics, the dimension of a vector space ''V'' is the cardinality (i.e., the number of vectors) of a basis of ''V'' over its base field. p. 44, §2.36 It is sometimes called Hamel dimension (after Georg Hamel) or algebraic dimension to di ...
s, the transpose is an operation on matrices that may be seen as the representation of some operation on linear maps. This leads to a much more general definition of the transpose that works on every linear map, even when linear maps cannot be represented by matrices (such as in the case of infinite dimensional vector spaces). In the finite dimensional case, the matrix representing the transpose of a linear map is the transpose of the matrix representing the linear map, independently of the
basis Basis may refer to: Finance and accounting * Adjusted basis, the net cost of an asset after adjusting for various tax-related items *Basis point, 0.01%, often used in the context of interest rates * Basis trading, a trading strategy consisting ...
choice.


Transpose of a linear map

Let denote the
algebraic dual space In mathematics, any vector space ''V'' has a corresponding dual vector space (or just dual space for short) consisting of all linear forms on ''V'', together with the vector space structure of pointwise addition and scalar multiplication by con ...
of an -
module Module, modular and modularity may refer to the concept of modularity. They may also refer to: Computing and engineering * Modular design, the engineering discipline of designing complex devices using separately designed sub-components * Mo ...
. Let and be -modules. If is a
linear map In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...
, then its algebraic adjoint or dual, is the map defined by . The resulting functional is called the
pullback In mathematics, a pullback is either of two different, but related processes: precomposition and fiber-product. Its dual is a pushforward. Precomposition Precomposition with a function probably provides the most elementary notion of pullback: i ...
of by . The following
relation Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...
characterizes the algebraic adjoint of : for all and where is the natural pairing (i.e. defined by ). This definition also applies unchanged to left modules and to vector spaces. The definition of the transpose may be seen to be independent of any bilinear form on the modules, unlike the adjoint ( below). The
continuous dual space In mathematics, any vector space ''V'' has a corresponding dual vector space (or just dual space for short) consisting of all linear forms on ''V'', together with the vector space structure of pointwise addition and scalar multiplication by const ...
of a
topological vector space In mathematics, a topological vector space (also called a linear topological space and commonly abbreviated TVS or t.v.s.) is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is als ...
(TVS) is denoted by . If and are TVSs then a linear map is weakly continuous if and only if , in which case we let denote the restriction of to . The map is called the transpose of . If the matrix describes a linear map with respect to bases of and , then the matrix describes the transpose of that linear map with respect to the dual bases.


Transpose of a bilinear form

Every linear map to the dual space defines a bilinear form , with the relation . By defining the transpose of this bilinear form as the bilinear form defined by the transpose i.e. , we find that . Here, is the natural
homomorphism In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
into the
double dual In mathematics, any vector space ''V'' has a corresponding dual vector space (or just dual space for short) consisting of all linear forms on ''V'', together with the vector space structure of pointwise addition and scalar multiplication by con ...
.


Adjoint

If the vector spaces and have respectively
nondegenerate In mathematics, a degenerate case is a limiting case of a class of objects which appears to be qualitatively different from (and usually simpler than) the rest of the class, and the term degeneracy is the condition of being a degenerate case. T ...
bilinear forms and , a concept known as the adjoint, which is closely related to the transpose, may be defined: If is a
linear map In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...
between
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
s and , we define as the adjoint of if satisfies :B_X\big(x, g(y)\big) = B_Y\big(u(x), y\big) for all and . These bilinear forms define an
isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
between and , and between and , resulting in an isomorphism between the transpose and adjoint of . The matrix of the adjoint of a map is the transposed matrix only if the bases are
orthonormal In linear algebra, two vectors in an inner product space are orthonormal if they are orthogonal (or perpendicular along a line) unit vectors. A set of vectors form an orthonormal set if all vectors in the set are mutually orthogonal and all of un ...
with respect to their bilinear forms. In this context, many authors however, use the term transpose to refer to the adjoint as defined here. The adjoint allows us to consider whether is equal to . In particular, this allows the orthogonal group over a vector space with a quadratic form to be defined without reference to matrices (nor the components thereof) as the set of all linear maps for which the adjoint equals the inverse. Over a complex vector space, one often works with
sesquilinear form In mathematics, a sesquilinear form is a generalization of a bilinear form that, in turn, is a generalization of the concept of the dot product of Euclidean space. A bilinear form is linear in each of its arguments, but a sesquilinear form allows o ...
s (conjugate-linear in one argument) instead of bilinear forms. The
Hermitian adjoint In mathematics, specifically in operator theory, each linear operator A on a Euclidean vector space defines a Hermitian adjoint (or adjoint) operator A^* on that space according to the rule :\langle Ax,y \rangle = \langle x,A^*y \rangle, where ...
of a map between such spaces is defined similarly, and the matrix of the Hermitian adjoint is given by the conjugate transpose matrix if the bases are orthonormal.


See also

*
Adjugate matrix In linear algebra, the adjugate or classical adjoint of a square matrix is the transpose of its cofactor matrix and is denoted by . It is also occasionally known as adjunct matrix, or "adjoint", though the latter today normally refers to a differe ...
, the transpose of the cofactor matrix *
Conjugate transpose In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex c ...
* Moore–Penrose pseudoinverse *
Projection (linear algebra) In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself (an endomorphism) such that P\circ P=P. That is, whenever P is applied twice to any vector, it gives the same result as if it wer ...


References


Further reading

* * . * * * *


External links

* Gilbert Strang (Spring 2010
Linear Algebra
from MIT Open Courseware {{Tensors Matrices Abstract algebra Linear algebra