02.2 Two consecutive conversions

Content and key concepts

On the previous page, the matrix changes space.
The common table can replace both steps, but the order of action is important.
First the turn, then the sprain.
Для изменения рисунка включитеJavaScript; расчёт и теория доступны далее.
Production arises from the composition of functions
Let it be applied first
B
B
B
and then
A
A
A
:
z
=
B
x
,
y
=
A
z
=
A
(
B
x
)
.
z=Bx,
\qquad y=Az=A(Bx).
z
=
B
x
,
y
=
A
z
=
A
(
B
x
)
.
We want to replace two consecutive operators with one.
C
C
C
so that
y
=
C
x
y=Cx
y
=
C
x
We'll set him up.
z
r
=
∑
j
=
1
n
B
r
j
x
j
z_r=\sum_{j=1}^{n}B_{rj}x_j
z
r
​
=
j
=
1
∑
n
​
B
r
j
​
x
j
​
in the formula for
y
i
y_i
y
i
​
:
y
i
=
∑
r
=
1
k
A
i
r
z
r
=
∑
r
=
1
k
A
i
r
∑
j
=
1
n
B
r
j
x
j
=
∑
j
=
1
n
(
∑
r
=
1
k
A
i
r
B
r
j
)
x
j
.
y_i=\sum_{r=1}^{k}A_{ir}z_r
=\sum_{r=1}^{k}A_{ir}\sum_{j=1}^{n}B_{rj}x_j
=\sum_{j=1}^{n}\left(\sum_{r=1}^{k}A_{ir}B_{rj}\right)x_j.
y
i
​
=
r
=
1
∑
k
​
A
i
r
​
z
r
​
=
r
=
1
∑
k
​
A
i
r
​
j
=
1
∑
n
​
B
r
j
​
x
j
​
=
j
=
1
∑
n
​
(
r
=
1
∑
k
​
A
i
r
​
B
r
j
​
)
x
j
​
.
Consequently,
A
∈
R
m
×
k
,
B
∈
R
k
×
n
,
C
=
A
B
∈
R
m
×
n
,
C
i
j
=
∑
r
=
1
k
A
i
r
B
r
j
.
A\in\mathbb R^{m\times k},
\quad B\in\mathbb R^{k\times n},
\quad C=AB\in\mathbb R^{m\times n},
\quad C_{ij}=\sum_{r=1}^{k}A_{ir}B_{rj}.
A
∈
R
m
×
k
,
B
∈
R
k
×
n
,
C
=
A
B
∈
R
m
×
n
,
C
ij
​
=
r
=
1
∑
k
​
A
i
r
​
B
r
j
​
.
Internal dimension
k
k
k
must match because it lists the components of the intermediate vector.
z
z
z
III. External dimensions
m
,
n
m,n
m
,
n
the size of the final operator.
Row-column trade without a hidden step
Here we go.
A
=
[
2
1
0
1
]
,
B
=
[
0
−
1
1
0
]
.
A=\begin{bmatrix}2&1\\0&1\end{bmatrix},
\qquad
B=\begin{bmatrix}0&-1\\1&0\end{bmatrix}.
A
=
[
2
0
​
1
1
​
]
,
B
=
[
0
1
​
−
1
0
​
]
.
Each cell
A
B
AB
A
B
is the dot line
A
A
A
and the column
B
B
B
:
A
B
=
[
2
⋅
0
+
1
⋅
1
2
⋅
(
−
1
)
+
1
⋅
0
0
⋅
0
+
1
⋅
1
0
⋅
(
−
1
)
+
1
⋅
0
]
=
[
1
−
2
1
0
]
.
AB=\begin{bmatrix}
2\cdot0+1\cdot1 & 2\cdot(-1)+1\cdot0\\
0\cdot0+1\cdot1 & 0\cdot(-1)+1\cdot0
\end{bmatrix}
=\begin{bmatrix}1&-2\\1&0\end{bmatrix}.
A
B
=
[
2
⋅
0
+
1
⋅
1
0
⋅
0
+
1
⋅
1
​
2
⋅
(
−
1
)
+
1
⋅
0
0
⋅
(
−
1
)
+
1
⋅
0
​
]
=
[
1
1
​
−
2
0
​
]
.
For example, an element
(
0
,
1
)
(0,1)
(
0
,
1
)
equal to
−
2
-2
−
2
not a work.
A
01
B
01
=
−
1
A_{01}B_{01}=-1
A
01
​
B
01
​
=
−
1
The component work of Adamar and matmul is a different operation, even for the same shapes.
Operators are read from right to left
In terms of
(
A
B
)
x
(AB)x
(
A
B
)
x
First action
B
B
B
I. INTRODUCTION
x
=
[
1
,
2
]
T
x=[1,2]^T
x
=
[
1
,
2
]
T
:
B
x
=
[
−
2
,
1
]
T
,
A
(
B
x
)
=
[
−
3
,
1
]
T
.
Bx=[-2,1]^T,
\qquad A(Bx)=[-3,1]^T.
B
x
=
[
−
2
,
1
]
T
,
A
(
B
x
)
=
[
−
3
,
1
]
T
.
Reverse order gives
B
A
=
[
0
−
1
2
1
]
,
B
A
x
=
[
−
2
,
4
]
T
.
BA=\begin{bmatrix}0&-1\\2&1\end{bmatrix},
\qquad BAx=[-2,4]^T.
B
A
=
[
0
2
​
−
1
1
​
]
,
B
A
x
=
[
−
2
,
4
]
T
.
So,
A
B
≠
B
A
AB\ne BA
A
B

=
B
A
B. Geometrically, "turn first, then perform shear/scale" is usually not equal to "reform, then turn".
Association does not mean commutability
Subject to compatible steps
A
(
B
C
)
=
(
A
B
)
C
.
A(BC)=(AB)C.
A
(
BC
)
=
(
A
B
)
C
.
Both sides describe one composition of three functions in one order. The brackets change only what intermediate work is calculated first.
[
m
,
k
]
[
k
,
n
]
[
n
,
p
]
[m,k][k,n][n,p]
[
m
,
k
]
[
k
,
n
]
[
n
,
p
]
The cost may vary markedly:
cost
⁡
(
(
A
B
)
C
)
∼
m
k
n
+
m
n
p
,
cost
⁡
(
A
(
B
C
)
)
∼
k
n
p
+
m
k
p
.
\operatorname{cost}((AB)C)\sim mkn+mnp,
\qquad
\operatorname{cost}(A(BC))\sim knp+mkp.
cost
((
A
B
)
C
)
∼
mkn
+
mn
p
,
cost
(
A
(
BC
))
∼
kn
p
+
mk
p
.
In exact arithmetic, the results are equal. In floating-point, a change in the order of summation may result in a slight discrepancy of rounding. This does not change algebraic association, but requires a tolerance with numerical comparison.
Identity Satisfied
A
I
=
I
A
=
A
AI=IA=A
A
I
=
I
A
=
A
The zero matrix of the right shape destroys the result. Transponder turns order:
(
A
B
)
T
=
B
T
A
T
.
(AB)^T=B^TA^T.
(
A
B
)
T
=
B
T
A
T
.
The last equality can be checked by index and it will be important for backward pass.
Direct work algorithm
[
m
,
k
]
×
[
k
,
n
]
[m,k]\times[k,n]
[
m
,
k
]
×
[
k
,
n
]
Demands
m
k
n
mkn
mkn
The parallel device changes the organization of computations and the movement of data, but not the cell formula. In the lab, choose one cell transfer and check the two pieces before comparing the completes.
A
B
AB
A
B
and
B
A
BA
B
A
.
A, B = [[2, 1], [0, 1]], [[0, -1], [1, 0]]
C = [[sum(A[i][r] * B[r][j] for r in range(2))
for j in range(2)] for i in range(2)]
assert C == [[1, -2], [1, 0]]
The code repeats the operations just taken care of.
Completely checked Python-example Chapter
Available with a separate file; the short piece shown does not replace its implementation.
If you change the order, you'll have another conversion, and it's also important for the neural layer.
When the direction is lost, how does this question continue?
Python examples of Chapter 02
Academic base