text:
© 2015-2017 <NAME>, <NAME>, and <NAME>

# Chapter 8: Rank

This chapter is about a concept called the rank, which is a property of a matrix. In fact, it reveals several aspects of a matrix. Some of the examples here may be shown for square matrices but everything in this chapter works for rectangular matrices, say of size $m \times n$. We start with an example from the application of structure from sound.

Example 8.1: Structure from Sound
There are many examples from applied mathematics, which involves the concept of rank. One such example is the so called structure from sound problem. In this example, sounds are recorded at a number of stationary, but unknown, microphone positions. Unknown sounds are emitted at unknown positions and at unknown times. It turns out that it is still possible to calculate (i) where the microphones are, (ii) how the sound source has moved, and (iii) when the sound sources were emitted, just using the measured sound signals from the microphones. Here rank plays an important role.
Figure 8.1: Illustration of the measurement situation. The sound source (held in the left hand) is moving, while the eight microphones are stationary.
Figure 8.1: Illustration of the measurement situation. The sound source (held in the left hand) is moving, while the eight microphones are stationary.
Figure 8.1 shows the measurement situation. Eight microphones capture the sound as a single sound source is moving in the room. The eight sound files are used to calculate the microphone positions and the sound source movement. See also the following YouTube clip. The 3D sound source path and the microphone locations that are computed are also visualized in Interactive Illustration 8.2.
Interactive Illustration 8.2: The blue circles represent where the eight microphones are located. However, these are unknown and so is the moving position of the sound source. Press/click forward to see the sound source path.
Interactive Illustration 8.2: The red sound source path and blue microphone positions were calculated from 30 seconds of sound recordings. Press the rotation icon in the top left corner to rotate the point cloud, or right-hand click plus drag to see the model from any orientation.
We start by explaining the null space, column space, and row space of a matrix. As will be shown these three spaces are themselves linear vector spaces. They are examples of linear subspaces, which are explained next.

A linear subspace of a vector space is a subset of the vectors that is itself a linear space. To show that a subset of a linear space is a linear subspace one only has to check three things. This is captured by the following theorem.

Theorem 8.1:
Let $V$ be a linear vector space over the scalars $F$. (Here we will typically only use $F=\R$ or $F=\mathbb{C}$). A subset $W \subset V$ is a linear vector space, i.e. a subspace, if and only if $W$ satisfies the following three conditions:
1. The zero vector $\vc{0} \in W$.
2. If $\vc{v}_1 \in W$ and $\vc{v}_2 \in W$ then $\vc{v}_1+\vc{v}_2 \in W$.
3. If $\vc{v} \in W$ and $\lambda \in F$ then $\lambda \vc{v}\in W$.

First, we prove that $W$ is a vector space if the conditions hold. By condition (i) we see that $W$ is nonempty. The conditions (ii) and (iii) ensure that the result of adding two vectors or multiplying a vector with a scalar does not take us outside the subset. Since the elements of $W$ are already part of vector space $V$, we then know that all the other rules Theorem 2.1 hold.

Second, we prove that if the subset $W$ is a vector space then the three conditions must hold. Since $W$ is a vector space, then the properties (ii) and (iii) are satisfied. Since $W$ is non-empty, there is at least one element $\vc{w}$. We can then form $\vc{0} = 0 \vc{w} \in W$. Thus property (i) holds.
$\square$

Example 8.2:
Let $\mx{A}$ be an $m \times n$ matrix. Let $V$ be the linear vector space $\R^n$. Let $W \subset V$ be the subset of vectors $\vc{v} \in V$ that fulfills $\mx{A}\vc{v} = \vc{0}$. Then $W$ is a linear vector space. This is true since
1. The zero vector $\vc{0} \in W$ since $\mx{A}\vc{0} = \vc{0}$.
2. If $\vc{v}_1 \in W$ and $\vc{v}_2 \in W$ then $\mx{A}(\vc{v}_1+\vc{v}_2) = \mx{A}\vc{v}_1+\mx{A}\vc{v}_2 = \vc{0}+\vc{0}$. Therefore $\vc{v}_1+\vc{v}_2 \in W$.
3. If $\vc{v} \in W$ and $\lambda \in F$ then $\mx{A}(\lambda \vc{v}) = \lambda \mx{A} \vc{v}= \lambda\vc{0} =\vc{0}$. Therefore $\lambda \vc{v}\in W$.
This means that the solutions to a homogeneous system is a linear space.

Example 8.3:
Let $\mx{A}$ be an $m \times n$ matrix. Let $V$ be the linear vector space $\R^m$. Let $W \subset V$ be the subset of vectors $\vc{v} \in V$ that can be generated as $\vc{v}= \mx{A}\vc{u}$ for some $\vc{u} \in \R^n$. Then $W$ is a linear vector space. This is true since
1. The zero vector $\vc{0} \in W$ since $\vc{0}\in\R^m$ can be generated from $\vc{0} \in \R^n$ by $\vc{0} =\mx{A}\vc{0}$.
2. If $\vc{v}_1 \in W$ and $\vc{v}_2 \in W$ then there exists $\vc{u}_1 \in \R^n$ and $\vc{u}_2 \in \R^n$ so that $\vc{v}_1 = \mx{A}\vc{u}_1$ and $\vc{v}_1 = \mx{A}\vc{u}_1$. But then $\vc{v}_1+\vc{v}_2 \in W$, since $(\vc{v}_1+\vc{v}_2) = \mx{A}\vc{u}_1+\mx{A}\vc{u}_2 = \mx{A}(\vc{u}_1 + \vc{u}_2)$.
3. If $\vc{u} \in W$ and $\lambda \in F$ then there exists $\vc{u} \in \R^n$ so that $\vc{v} = \mx{A}\vc{u}$ . But then $\lambda \vc{v}\in W$ since $\lambda \vc{v} = \lambda \mx{A}(\vc{u}) = \mx{A} (\lambda \vc{u})$.
This means that the set of linear combinations of a set of vectors is a linear space.

As we have seen in Section 5.5, a system of equations such as $\mx{A}\vc{x} = \vc{0}$ is called homogeneous. We will now show that the solutions to such systems reveal certain useful properties of $\mx{A}$. Let us start with an example. Assume we have a matrix
 $$\mx{A} = \begin{pmatrix} 2 & \hid{-}5 & \hid{-}3 \\ 4 & \hid{-}2 & \hid{-}1 \\ 2 & -3 & -2 \end{pmatrix},$$ (8.1)
and that we want to solve for $\mx{A}\vc{x}=\vc{0}$, where $\vc{x} = (x_1, x_2, x_3)$ is a column vector. This is the same example as in Equation (5.34), i.e.,
 $$\begin{cases} \begin{array}{rrrl} 2 x_1 + 5 & \bs x_2 + 3 & \bs x_3 = 0, \\ 4 x_1 + 2 & \bs x_2 +\hid{3}& \bs x_3 = 0, \\ 2 x_1 - 3 & \bs x_2 - 2 & \bs x_3 = 0, \\ \end{array} \end{cases}$$ (8.2)
After some work with Gaussian elimination, we arrived at
 $$\begin{cases} \begin{array}{rrrl} 2 x_1 + 5 & \bs x_2 + 3 & \bs x_3 = 0, \\ 8 & \bs x_2 + 5 & \bs x_3 = 0, \\ & & \bs 0 = 0. \\ \end{array} \end{cases}$$ (8.3)
The next step is then to set $x_3=t$, which means that $x_2=-\frac{5}{8}t$, and finally, $x_1=\frac{1}{16}t$, i.e.,
 $$\vc{x}(t) = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} \frac{1}{16}t \\ -\frac{5}{8}t \\ t \end{pmatrix}$$ (8.4)
As can be seen, the solution is a line which is dependent only on one varying parameter $t$. Sometimes the solution is denoted by $\vc{x}_\mathrm{h}$ to indicate that it is a solution to the homogeneous system $\mx{A}\vc{x}=\vc{0}$. This entire set of solutions is called the null space of $\mx{A}$ and in this particular case, the dimension of the null space is 1, since it only depends on one parameter, namely $t$. We also use the term null vector for $(1/16, -5/8, 1)$. Next, this is formalized into a definition.

Definition 8.1: Null Space
If $\mx{A}$ is an $m\times n$ matrix (i.e., with $m$ rows and $n$ columns), then the entire set of solutions to $\mx{A}\vc{x}=\vc{0}$ is called the null space of $\mx{A}$.
By definition, the null space must be a subspace of $\R^n$, that is, $\nullity(\mx{A}) \leq n$. It is a linear subspace, (see Example 8.2). The dimension of this subspace is important and has its own definition.

Definition 8.2: Nullity
The dimension of the null space is denoted $\nullity(\mx{A})$.
Since the null space is a subspace of $\R^n$, we have $\nullity(\mx{A}) \leq n$. But how many dimensions lower is the null space? This is captured loosely by the number of constraints in $\mx{A}\vc{x}=\vc{0}$, however, here we must be careful. Just because there are $m$ equations in $\mx{A}\vc{x}=\vc{0}$ it does not automatically mean that $\nullity(\mx{A}) = n - m$. How many constraints there are in $\mx{A}$ is precisely what is captured by the concept of rank. What we are later going to show is that $\nullity(\mx{A}) = n - r$, i.e., that the dimension is lowered by $r$ (i.e., the rank of $\mx{A}$) using the constraints in $\mx{A}\vc{x}=\vc{0}$.

Definition 8.3: Null Vectors
Let $\vc{p}_1, \ldots, \vc{p}_k$ be a basis for the null space. A solution, $\vc{x}$, is on the form $\vc{x}(t_1,\dots t_k) = t_1\vc{p}_1 + \dots + t_k\vc{p}_k$, where $k$ is the dimension of the null space. The basis vectors $\vc{p}_i$ are sometimes called null vectors, although sometimes any vector in the null space is called a null vector.
Using Gaussian elimination, we obtain a basis for the null space and thereby also the dimension of the null space. It is the number of independent parameters in the solution to $\mx{A}\vc{x}=\vc{0}$ that dictates the dimension of the null space.

Example 8.4: Null Space
Here, we will again look a the solution of a system of equations on the form $\mx{A}\vc{x}=\vc{0}$. The following system of equations
 $$\begin{cases} \begin{array}{rrrrrl} 2 x_1\hid{+} & \bs \hid{x_2} + \hid{1} & \bs x_3 - 2 & \bs x_4 +\hid{1} & \bs x_5 = 0, \\ 2 x_1+ & \bs x_2 + 5 & \bs x_3 \hid{+}\hid{2} &\bs \hid{x_4} + 2 & \bs x_5 = 0, \\ & \bs x_2+ 4 & \bs x_3 + 2 & \bs x_4 +\hid{1} & \bs x_5 = 0, \\ & & \hid{1} & \bs x_4 + 2 & \bs x_5 = 0, \\ \end{array} \end{cases}$$ (8.5)
can be rewritten as
 $$\underbrace{ \left( \begin{array}{rrrrr} 2 & 0 & 1 & -2 & 1 \\ 2 & 1 & 5 & 0 & 2 \\ 0 & 1 & 4 & 2 & 1 \\ 0 & 0 & 0 & 1 & 2 \\ \end{array} \right) }_{\mx{A}} \underbrace{ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ \end{pmatrix} }_{\vc{x}} = \underbrace{ \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} }_{\vc{0}}.$$ (8.6)
Next, we will use the compact notation used in Example 6.11 to solve $\mx{A}\vc{x}=\vc{0}$ using Gaussian elimination,
 $$\left( \begin{array}{rrrrr|r} 2 & 0 & 1 & -2 & 1 & 0\\ 2 & 1 & 5 & 0 & 2 & 0\\ 0 & 1 & 4 & 2 & 1 & 0\\ 0 & 0 & 0 & 1 & 2 & 0\\ \end{array} \right) \Leftrightarrow \left( \begin{array}{rrrrr|r} 2 & 0 & 1 & -2 & 1 & 0\\ 0 & 1 & 4 & 2 & 1 & 0\\ 0 & 1 & 4 & 2 & 1 & 0\\ 0 & 0 & 0 & 1 & 2 & 0\\ \end{array} \right),$$ (8.7)
where the step above subtracted row 1 from row 2. As can be seen, row 2 and 3 are now identical, which means that we will obtain a row of zeroes when they are subtracted, i.e.,
 $$\left( \begin{array}{rrrrr|r} 2 & 0 & 1 & -2 & 1 & 0\\ 0 & 1 & 4 & 2 & 1 & 0\\ 0 & 0 & 0 & 1 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ \end{array} \right).$$ (8.8)
As we saw in Section 5.5, the procedure in cases such as this is now to set one parameter to being variable, for example, $x_5=t$. Using row 3, we get $x_4+2x_5=0$, that is, $x_4=-2t$. For row 2, we need to introduce one more variable parameter, say, $x_3=s$, which gives us $x_2 = -4s + 3t$. Finally, using row 1, we can get $x_1 = -\frac{1}{2}s-\frac{5}{2}t$. The solution is then
 $$\vc{x}_\mathrm{h} = s \underbrace{ \left( \begin{array}{r} -\frac{1}{2} \\ -4 \\ 1 \\ 0 \\ 0 \\ \end{array} \right) }_{\vc{m}} + t \underbrace{ \left( \begin{array}{r} -\frac{5}{2} \\ 3 \\ 0 \\ -2 \\ 1 \\ \end{array} \right) }_{\vc{n}} =s\vc{m} + t\vc{n}.$$ (8.9)
Per Definition 8.1, the solution above is the null space of $\mx{A}$ and since it depends on two variables $s$ and $t$, we know that the dimension of the null space is 2, that is, $\nullity(\mx{A})=2$. Furthermore, we also say that the vectors $\vc{m}$ and $\vc{n}$ span the null space, i.e., they are basis vectors for the null space.

For an $m\times n$ matrix $\mx{A}$, recall from Definition 6.2 how the rows $\vc{a}_{i,}^\T$, where $i\in{1,\dots,m}$, and the columns, $\vc{a}_{,j}$, are accessed, i.e.,
 $$\mx{A} = \bigl(\vc{a}_{,1} \,\,\, \vc{a}_{,2} \,\,\,\dots\,\,\, \vc{a}_{,n}\bigr) = \left( \begin{array}{c} \vc{a}_{1,}^\T\\ \vc{a}_{2,}^\T\\ \vdots \\ \vc{a}_{m,}^\T\\ \end{array} \right).$$ (8.10)
In addition, we repeat that the notation of column and row vectors in this book, i.e., all vectors are column vectors by default and if you want to use a row vector, you take a column vector, $\vc{x}$, and you transpose it to get a row vector, $\vc{x}^\T$. Also, $(x_1,x_2,x_3)$ is also a column vector (note the commas), while $(x_1 \spc x_2 \spc x_3)$ is a row vector, which is described below Definition 2.5.

Now that the null space is known, two related concepts, namely the column space and the row space, can be introduced.

Definition 8.4: Column Space
Let $\mx{A}= \left(\vc{a}_{,1} \vc{a}_{,2} \dots \vc{a}_{,n}\right)$ be an $m\times n$ matrix. The column space of $\mx{A}$ is then the set of all linear combinations of the column vectors, $\vc{a}_{,i}$.
Now, we note that matrix-vector multiplication, $\mx{A}\vc{x}$, can be expressed as
 $$\mx{A}\vc{x}= \left(\vc{a}_{,1}\,\,\, \vc{a}_{,2}\,\,\, \dots\,\,\, \vc{a}_{,n}\right)\vc{x} = x_1\vc{a}_{,1} + x_2\vc{a}_{,2} + \dots +x_n\vc{a}_{,n},$$ (8.11)
that is, as a linear combination (see Definition 5.1) of the column vectors of $\mx{A}$. So, the column space is therefore all the vectors that can be created by taking a constant times the first column vector plus another constant times the second column vector and so on. Note that the column space is a subspace of $\R^m$ by definition, since the number of elements in all column vectors of $\mx{A}$ is $m$.

Definition 8.5: Row Space
Let $\mx{A}= \left(\begin{array}{c} \vc{a}_{1,}^\T\\ \vc{a}_{2,}^\T\\ \vdots \\\vc{a}_{m,}^T \end{array}\right)$ be an $m\times n$ matrix. The row space of $\mx{A}$ is then the set of all linear combinations of the row vectors, $\vc{a}_{i,}^\T$.
Similar to the column space, we can write this as a vector-matrix multiplication, but this time we use a row vector $\vc{x}^\T$ with $m$ elements and multiply from the right, i.e.,
 $$\vc{x}^\T\mx{A}= \vc{x}^\T \left(\begin{array}{c} \vc{a}_{1,}^\T\\ \vc{a}_{2,}^\T\\ \vdots \\\vc{a}_{m,}^T \end{array}\right) = \left(\begin{array}{c} x_1\ \ x_2\ \ \dots\ \ x_m \end{array}\right) \left(\begin{array}{c} \vc{a}_{1,}^\T\\ \vc{a}_{2,}^\T\\ \vdots \\\vc{a}_{m,}^T \end{array}\right) = x_1\vc{a}_{1,}^\T + x_2 \vc{a}_{2,}^\T + \dots + x_m \vc{a}_{m,}^\T.$$ (8.12)
So, this is also a linear combination (see Definition 5.1), but this time using the row vectors of $\mx{A}$. So, the row space is therefore all the vectors that can be created by taking a constant times the first row vector plus another constant times the second row vector and so on. Note that the row space is a subspace of $\R^n$ by definition, since the number of elements in all row vectors of $\mx{A}$ is $n$.

Example 8.5: Column Space 1
In this example, we continue with the matrix from Example 8.4. Recall that we transformed the system of equations into
 $$\left( \begin{array}{rrrrr|r} 2 & 0 & 1 & -2 & 1 & 0\\ 0 & 1 & 4 & 2 & 1 & 0\\ 0 & 0 & 0 & 1 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ \end{array} \right).$$ (8.13)
The null space for this example was calculated in the previous example and here, we will show how the column space is obtained. As it turns out, the basis vectors for the column space can be directly "fetched" from the matrix above, where we have used Gaussian elimination to find the solution. The column vectors that form the column space are the ones with the first non-zero element of each row. Hence, we obtain the following vectors,
 \begin{align} \begin{pmatrix} 2 \\ 0 \\ 0 \\ 0 \end{pmatrix} , \ \ \ \ \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} , \ \ \ \ \mathrm{and}\ \ \ \ \left( \begin{array}{r} -2 \\ 2 \\ 1 \\ 0 \end{array} \right). \end{align} (8.14)
Since there are three basis vectors for the column space, the dimension of $\mx{A}$'s column space is also 3. The reason why this method works will be explained later in this chapter.

Example 8.6: Column Space 2
Assume we have
 $$\mx{A} = \left(\vc{a}_{,1}\,\,\, \vc{a}_{,2}\,\,\, \vc{a}_{,3}\right)= \left( \begin{array}{rrr} 1 & \hid{-}4 & -10 \\ 2 & \hid{-}1 & 1\\ 3 & -3 & 15 \end{array} \right).$$ (8.15)
Since one can verify that $\vc{a}_{,3} = 2\vc{a}_{,1}-3\vc{a}_{,2}$, the column space is at most a linear combination of two vectors. This means that if $\vc{a}_{,1}$ is parallel to $\vc{a}_{,2}$ then the column space is just dependent on one vector and otherwise, it is dependent on two. If $\vc{a}_{,1}$ is parallel to $\vc{a}_{,2}$, then $\vc{a}_{,1} \cdot \vc{a}_{,2}= \ln{\vc{a}_{,1}} \ln{\vc{a}_{,2}}$ (see Definition 3.1). Since $\vc{a}_{,1} \cdot \vc{a}_{,2} = 1\cdot 4 + 2\cdot 1 + 3\cdot(-3) = -3$ and $\ln{\vc{a}_{,1}} \ln{\vc{a}_{,2}}\geq 0$, we draw the conclusions that they are not parallel and that the column space is a combination of two vectors. For example, the column space can be expressed as
 $$s \begin{pmatrix} 1\\ 2\\ 3 \end{pmatrix} +t \left( \begin{array}{r} 4\\ 1\\ -3 \end{array} \right),$$ (8.16)
where $s$ and $t\in \R$. i.e., the column space is a linear combination of $\vc{a}_{,1}$ and $\vc{a}_{,2}$. As we will see later, this means that $\rank(\mx{A})=2$, since the column space is a linear combination of two vectors. Geometrically, this means that the column space is a plane (see Definition 3.8), which also is clear from Equation (8.16).

Definition 8.6: Row and Column Rank
Let $\mx{A}$ be a matrix. The row rank of $\mx{A}$, denoted $\rowrank(\mx{A})$, is the maximum number of linearly independent row vectors of $\mx{A}$. Similarly, the column rank, denoted $\colrank(\mx{A})$, is the maximum number of linearly independent column vectors of $\mx{A}$.
In the following, we will go through a number of steps that will lead up to a point where we easily can obtain the column/row vectors of the column/row space of a matrix. We start with the following theorem.

Theorem 8.2:
Neither of the operations of Gaussian elimination (Theorem 5.2) changes the row space of an $m \times n$ matrix $\mx{A}$ after applying the operation.

The rows of $\mx{A}$ are denoted $\vc{a}_{i,}^{\T}$ where $i\in\{1,\dots, m\}$ as usual. In this proof, we use the following notation for the operations of Theorem 5.2
1. $(i)$: $\vc{a}_{i,}^{\T} \leftrightarrow \vc{a}_{j,}^{\T}$ to indicate that the order of two rows are swapped,
2. $(ii)$: $\vc{a}_{i,}^{\T} \rightarrow k\vc{a}_{i,}^{\T}$ to indicate that a row is multiplied by a non-zero constant, $k$, and
3. $(iii)$: $\vc{a}_{i,}^{\T} \rightarrow \vc{a}_{i,}^{\T} + \vc{a}_{j,}^{\T}$ for addition of one row to another.
$(i)$: It is clear that when the first rule is applied only the order of the rows change and thus, the row space stays the same.
$(ii)$: For this rule, the matrix before and after applying the rule are the same except on row $i$. Now, recall from Equation (8.12) that the row space is expressed as
 $$\underbrace{ k_1 \vc{a}_{1,}^{\T} + \dots + k_i \vc{a}_{i,}^{\T} + \dots + k_m \vc{a}_{m,}^{\T} }_{\mathrm{row\ space}},$$ (8.17)
which can be rewritten as
 \begin{gather} k_1 \vc{a}_{1,}^{\T} + \dots + k_i \vc{a}_{i,}^{\T} + \dots + k_m \vc{a}_{m,}^{\T}\\ \Longleftrightarrow \\ k_1 \vc{a}_{1,}^{\T} + \dots + \left(\frac{k_i}{k}\right) \left( k \vc{a}_{i,}^{\T}\right) + \dots + k_m \vc{a}_{m,}^{\T}. \end{gather} (8.18)
Since we can think of $k \vc{a}_{i,}^{\T}$ as a "new" row vector and $k_i/k$ as an arbitrary constant before the new row vector, it is clear that everything that can be expressed in the first line of Equation (8.18) can also be expressed in the last line of Equation (8.18), and vice versa. Hence, the second rule preserves the row space.
$(iii)$: With the third rule $\vc{a}_{i,}^{\T} \rightarrow \vc{a}_{i,}^{\T} + \vc{a}_{j,}^{\T}$, we rewrite Equation (8.17) as
 \begin{gather} k_1 \vc{a}_{1,}^{\T} + \dots + k_i \vc{a}_{i,}^{\T} + \dots + k_j \vc{a}_{j,}^{\T} + \dots + k_m \vc{a}_{m,}^{\T}\\ \Longleftrightarrow \\ k_1 \vc{a}_{1,}^{\T} + \dots + k_i (\vc{a}_{i,}^{\T} + \vc{a}_{j,}^{\T}) + \dots + (k_j-k_i) \vc{a}_{j,}^{\T} + \dots + k_m \vc{a}_{m,}^{\T}. \end{gather} (8.19)
Here, $\vc{a}_{i,}^{\T} + \vc{a}_{j,}^{\T}$ is the updated row vector and as can be seen, the constant before $\vc{a}_{j,}^{\T}$ has changed to $k_j - k_i$, and hence any value can be obtained by changing $k_j$ appropriately. As a conclusion, we now know that the row space of $\mx{A}$ is in the row space of matrix obtained after using rule $(iii)$. However, we need to show the rule in the other direction $(\leftarrow)$ as well. Since
 \begin{gather} k_1 \vc{a}_{1,}^{\T} + \dots + k_i (\vc{a}_{i,}^{\T} + \vc{a}_{j,}^{\T}) + \dots + k_j \vc{a}_{j,}^{\T} + \dots + k_m \vc{a}_{m,}^{\T}\\ \Longleftrightarrow \\ k_1 \vc{a}_{1,}^{\T} + \dots + k_i \vc{a}_{i,}^{\T} + \dots + (k_j+k_i) \vc{a}_{j,}^{\T} + \dots + k_m \vc{a}_{m,}^{\T}, \end{gather} (8.20)
by similar arguments, the row space of a matrix with rule $(iii)$ applied is in the row space of the original matrix. This concludes the proof.
$\square$

Note that it is important that Theorem 8.2 only works for the row space and not for the column space.

In the following, it will be useful to have a specific term for the matrix that is obtained after Gaussian elimination. This is described in the following definition.

Definition 8.7: Row Echelon Form of a Matrix
A matrix $\mx{A}$ is said to be on row echelon form if its rows with only zeroes (if any) are placed at the bottom, and the first non-zero coefficient, $a_{ij}$, on each row with number $i$ is placed such that all other rows with a first non-zero coefficient, $a_{i'j'}$, fulfills $i' < i$ (the row $i'$ is above row $i$) and $j' < j$.
Note that a matrix on row echelon form can be obtained by applying Gaussian elimination until no more reductions can be made. This gives a triangular-like structure for matrices on row echelon form, e.g.,
 $$\left( \begin{array}{rrrrr} \underline{2} & 0 & 1 & -2 & 1 \\ 0 & \underline{1} & 4 & 2 & 1 \\ 0 & 0 & 0 & \underline{1} & 2 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right).$$ (8.21)
Therefore, this type of matrices are sometimes said to be a "staircase equivalent" matrix of $\mx{A}$. The leading non-zero coefficients, underlined in the previous equation, are important. These elements of the matrix are often called pivot element. Some texts require that these leading non-zero coefficients are made to ones. This can be achieved by dividing the entire row by the leading non-zero coefficient. However, we do not require that here.

Next, we present a theorem that says how the row space basis vectors can be found and how the dimension of the row space is found.

Theorem 8.3:
Given a system $\mx{A}\vc{x}=\vc{0}$, which after Gaussian elimination is on row echelon form $\mx{R}\vc{x}=\vc{0}$, i.e., $\mx{A}\vc{x} = \vc{0} \Longleftrightarrow \mx{R}\vc{x} = \vc{0}$, then
1. the non-zero rows of $\mx{R}$ form a basis for the row space of $\mx{R}$ and due to Theorem 8.2 also for $\mx{A}$, and
2. the column vectors with the first non-zero element of the row vectors form the column space basis of $\mx{R}$, while the column space for $\mx{A}$ is the column vectors from $\mx{A}$ with the column numbers as the columns for the column space for $\mx{R}$.

To show that the non-zero rows are a basis we need to show (i) that they span the space and (ii) that they are independent.
(i) That any combination of the rows are also combination of the non-zero rows is clear. Therefore the non-zero rows span the row space.
(ii) To show that they are independent. No nonzero row of the row echelon matrix is a combination of the other rows since in the column of its leading 1, the other rows are 0. Hence the nonzero rows are independent.
$\square$

Note that the number of basis vector of the row/column space is the row/column rank.

Next, we will show that the dimension of the row space (i.e., the row rank) is the same as the dimension of the column space (i.e., the column rank). After the following theorem, we will give an example of how the row and column space basis can be found.

Theorem 8.4: Column and Row Rank Size
The row rank is equal to the column rank of a matrix $\mx{A}$.

Let us say that the row rank of $\mx{A}$ is $k$ and that $\{ \vc{b}_{1,}^\T,\dots,\vc{b}_{k,}^\T \}$ is a row space basis for $\mx{A}$. The $i$:th row of $\mx{A}$ is $\vc{a}_{i,}^\T = \left(a_{i1}, a_{i2},\dots,a_{in} \right)^\T$ and it can also be written using the row space basis vectors as $\vc{a}_{i,}^\T = \sum_{r=1}^k c_{ir} \vc{b}_{r,}^\T$, for some set of constants, $c_{ir}$. The $j$:th element of $\vc{a}_{i,}^\T$ is then
 $$a_{ij} = \sum_{r=1}^k c_{ir} b_{rj},$$ (8.22)
which is true for any column number, $j$. Hence, the $j$:th column vector is
 $$\vc{a}_{,j} = \begin{pmatrix} a_{1j}\\ \vdots \\ a_{mj} \end{pmatrix} = \sum_{r=1}^k b_{rj} \vc{d}_{r}, \ \ \mathrm{where}\ \ \vc{d}_{r} = \begin{pmatrix} c_{1r} \\ \vdots \\ c_{mr} \end{pmatrix}.$$ (8.23)
An interpretation of this is that every column of $\mx{A}$ is a linear combination of $k$ vectors, which means that the $\colrank(\mx{A})$ can be at most $k$. Expressed differently, we have $\colrank(\mx{A}) \leq \rowrank(\mx{A})$. If we apply this to the transpose of $\mx{A}$ then we have $\colrank(\mx{A}^\T) \leq \rowrank(\mx{A}^\T)$ which is the same as $\rowrank(\mx{A}) \leq \colrank(\mx{A})$, and since we had $\colrank(\mx{A}) \leq \rowrank(\mx{A})$ to start with, it follows that $\rowrank(\mx{A}) = \colrank(\mx{A})$.
$\square$

Hereafter, we do not need to distinguish between $\rowrank(\mx{A})$ and $\colrank(\mx{A})$, and instead, we refer to it as just rank, denoted $\rank(\mx{A})$. Note also that the theorem above can be stated as $\rank(\mx{A})= \rank(\mx{A}^{\T})$. This means that if you want to find the column space vectors of a matrix $\mx{A}$, then you can transpose it to $\mx{A}^{\T}$ and then use Theorem 8.3. Next, we show an example of how the column space basis can be found.

Example 8.7:
From Example 8.4, we have
 $$\underbrace{ \left( \begin{array}{rrrrr|r} 2 & 0 & 1 & -2 & 1 & 0\\ 2 & 1 & 5 & 0 & 2 & 0\\ 0 & 1 & 4 & 2 & 1 & 0\\ 0 & 0 & 0 & 1 & 2 & 0\\ \end{array} \right) }_{\mx{A}} \Leftrightarrow \underbrace{ \left( \begin{array}{rrrrr|r} 2 & 0 & 1 & -2 & 1 & 0\\ 0 & 1 & 4 & 2 & 1 & 0\\ 0 & 0 & 0 & 1 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ \end{array} \right) }_{\mx{R}}.$$ (8.24)
Using Theorem 8.3 (bullet 1), we find the row basis vector from $\mx{R}$ as
 \begin{gather} \begin{pmatrix} 2 & 0 & 1 & -2 & 1 \end{pmatrix} \\ \begin{pmatrix} 0 & 1 & 4 & 2 & 1 \end{pmatrix} \\ \begin{pmatrix} 0 & 0 & 0 & 1 & 2 \end{pmatrix}, \end{gather} (8.25)
since those are non-zero rows of $\mx{R}$. Hence, the $\rank(\mx{A})=3$.

Theorem 8.3 (bullet 2) also teaches us that the basis vectors for the column space of $\mx{R}$ are
 $$\left(\begin{array}{c} 2 \\ 0 \\ 0 \\ 0 \end{array} \right), \ \ \ \left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array} \right), \ \ \ \textrm{and}\ \ \ \left(\begin{array}{r} -2 \\ 2 \\ 1 \\ 0 \end{array} \right),$$ (8.26)
i.e., you look at each row and find the first non-zero element and take that column vector where this element resides. The column space for $\mx{A}$ is obtained using the column vectors with the same column number as the column vectors for for column space for $\mx{R}$, i.e.,
 $$\left(\begin{array}{c} 2 \\ 2 \\ 0 \\ 0 \end{array} \right), \ \ \ \left(\begin{array}{c} 0 \\ 1 \\ 1 \\ 0 \end{array} \right), \ \ \ \textrm{and}\ \ \ \left(\begin{array}{r} -2 \\ 0 \\ 2 \\ 1 \end{array} \right).$$ (8.27)
Since the column space is spanned by the three vectors above, we have $\rank(\mx{A})=3$ also when using the column space. This is to be expected since $\colrank(\mx{A})=\rowrank(\mx{A})$.

Theorem 8.5:
The rank of a matrix is the number of pivot elements after Gaussian elimination.

The row rank of a matrix $\mx{A}$ is equal to the dimension of the row space of the reduced matrix $\mx{R}$ after Gaussian elimination. Since a basis of the row space of $\mx{R}$ consists of those rows that have a pivot element, the dimension and thereby the rank is the number of pivot elements.
$\square$

Next, we present a theorem that provides an upper bound of the rank of a matrix-matrix product.

Theorem 8.6: Rank of Product
The rank of a product $\mx{A} = \mx{B} \mx{C}$ is less than or equal to the rank of the terms, i.e.,
 $$\rank \mx{A} \leq \rank \mx{C},$$ (8.28)
and
 $$\rank \mx{A} \leq \rank \mx{B}.$$ (8.29)

As we showed earlier, each row of the product $\mx{A}$ is a linear combination of the rows in $\mx{C}$. This means that all rows of $\mx{A}$ lies in the rowspace of $\mx{C}$, which means that $\rank \mx{A} \leq \rank \mx{C}$. Thus we have shown that the rank of a product is less than or equal to the rank of its rightmost term.
The other equality follows from studying the rows of $\mx{A}$ that are linear combination of the rows of $\mx{B}$. Alternatively the other equality can be proved using $\mx{A}^T = \mx{C}^T \mx{B}^T$. Here the rightmost term is $\mx{B}^T$. So $\rank \mx{A}^T \leq \rank \mx{B}^T$. But then we have $\rank \mx{A} = \rank \mx{A}^T \leq \rank \mx{B}^T = \rank \mx{B}$.
$\square$

Theorem 8.7:
Let $\vc{x}_\mathrm{h}$ be the solution to $\mx{A}\vc{x}=\vc{0}$ and let $\vc{x}_\mathrm{p}$ be the solution to a particular system of equations $\mx{A}\vc{x}=\vc{y}$, in which case the "entire" solution to $\mx{A}\vc{x}=\vc{y}$ is
 $$\vc{x}_{\mathrm{tot}} = \vc{x}_\mathrm{p} + \vc{x}_\mathrm{h}.$$ (8.30)

We know that $\mx{A}\vc{x}_\mathrm{h}=\vc{0}$ and $\mx{A}\vc{x}_\mathrm{p}=\vc{y}$. The theorem is proved by
 \begin{gather} \mx{A}\vc{x}_\mathrm{p}=\vc{y} \\ \Longleftrightarrow \\ \mx{A}\vc{x}_\mathrm{p} + \vc{0}=\vc{y} \\ \Longleftrightarrow \\ \mx{A}\vc{x}_\mathrm{p} + \mx{A}\vc{x}_\mathrm{h} =\vc{y} \\ \Longleftrightarrow \\ \mx{A}(\underbrace{\vc{x}_\mathrm{p} + \vc{x}_\mathrm{h}}_{\vc{x}_{\mathrm{tot}}}) =\vc{y}. \end{gather} (8.31)
$\square$

Now, we know that $\vc{x}_h$ is in the null space of $\mx{A}$ and that $\vc{y}$ must be in the column space of $\mx{A}$, otherwise it is not a solution to $\mx{A}\vc{x}=\vc{y}$. In Interactive Illustration 8.3, we show how these two solutions may interact.
$\vc{x}_h$
$\vc{x}_p$
$\vc{x}_{\mathrm{tot}}$
Interactive Illustration 8.3: Assume that we have a homogeneous system $\mx{A}\vc{x}=\vc{0}$ and we call the solutions to this $\vc{x}_h$. In this case, the set of solutions is a line as we can see above. Pull the slider to change the location of $\vc{x}_h$. Then click/touch Forward to proceed.
Interactive Illustration 8.3: Assume that we have a homogeneous system $\hid{\mx{A}\vc{x}=\vc{0}}$ and we call the solutions to this $\hid{\vc{x}_h}$. In this case, the set of solutions is a line as we can see above. Pull the slider to change the location of $\hid{\vc{x}_h}$. Then click/touch Forward to proceed.
The dimension theorem below is very handy since if you know either the dimension of the null space or the rank then you can find the other one of these (assuming you know the number of rows in the matrix, which is a reasonable assumption).

Theorem 8.8: Dimension Theorem
For an $m\times n$ matrix $\mx{A}$, i.e., with $n$ columns, it holds that
 $$\rank(\mx{A}) + \nullity(\mx{A}) = n.$$ (8.32)

If $\rank(\mx{A})=n$, this is the same as being able to invert the matrix since its determinant will be non-zero. There are therefore no other solutions to $\mx{A}\vc{x}=\vc{0}$ than $\vc{x}=\vc{0}$, i.e., $\nullity(\mx{A})=0$, which means $\rank(\mx{A})+0=n$. Hence, the theorem holds for that case. Next, we assume that $\rank(\mx{A}) < n$. In this case, there must be $n-r$ free variables in the solution to $\mx{A}\vc{x}=\vc{0}$. By free variables we mean $s$ and $t$ in Example 8.4, for example. Let us call the free variables $s_1$, $\dots$, $s_{n-r}$. There are $n-r$ linearly independent null vectors, which we denote by $\vc{x}_1$, $\dots$, $\vc{x}_{n-r}$. As we know, the solutions to $\mx{A}\vc{x}=\vc{0}$ are dictated by
 $$\vc{x} = s_1\vc{x}_1 + \dots + s_{n-r}\vc{x}_{n-r}.$$ (8.33)
Hence, $\vc{x}_1$, $\dots$, $\vc{x}_{n-r}$ is a basis for the null space and $\nullity(\mx{A}) = n-r$, which proves the theorem.
$\square$

Recall that $\nullity(\mx{A})$ dictates the number of parameters needed to describe the solution to the homogeneous system $\mx{A}\vc{x}=\vc{0}$ and that $\rank(\mx{A})$ is the number of linearly independent right-hand sides $\vc{y}$ when $\mx{A}\vc{x}=\vc{y}$ has a solution. Finally, the sum of these two numbers is $n$, i.e., the number of columns of $\mx{A}$.

Example 8.8: Dimension Theorem
In Example 8.4 and Example 8.7, we had a $4\times 5$ matrix $\mx{A}$, i.e., $m=4$ and $n=5$. We first saw that
 $$\nullity(\mx{A}) = 2$$ (8.34)
and then that
 $$\rank(\mx{A}) = 3.$$ (8.35)
The Dimension Theorem 8.8 states that $2+3=n$, where $n$ is the number of columns of the matrix. As can be seen, this is correct since $m=5$ is the number of coolumns of the matrix.
Note that $\mx{A}$ can be thought of as a transform or linear mapping (see Chapter 9), and that $n$ is the dimension of the domain of $\mx{A}$. Given this, we can think of $\rank(\mx{A})$ as the number of dimensions that "survive" after applying $\mx{A}$ and $\nullity(\mx{A})$ is the number of dimensions that are "collapsed" by $\mx{A}$.

Example 8.9: Orthogonal Projection of a Point onto a Plane - revisited
In Example 3.10, a point $P$ was projected onto a plane defined by a normal vector $\vc{n}$ and a point on the plane $S$, which we in this example assume is the origin, $O$. We found that $P$ projected orthogonally down to the plane can be expressed as
 $$Q = P - \proj{\vc{n}}{\vc{v}},$$ (8.36)
where $Q$ is the projected point and $\vc{v}=P-O$. The orthogonal projection formula (Definition 3.2) is $\proj{\vc{n}}{\vc{v}} = \left((\vc{v} \cdot \vc{n})/\ln{\vc{n}}^2\right) \vc{n}$ and as a result, the expression for $Q$ can be rewritten as
 $$Q = P - \frac{\vc{v} \cdot \vc{n}}{\vc{n} \cdot \vc{n}} \vc{n}.$$ (8.37)
In order to operate with matrices, we need to use vectors instead of points, so we introduce $\vc{q} = \overrightarrow{OQ}$ and we already have $\vc{v} = \overrightarrow{OP}$. This leads to
 \begin{align} \vc{q} &= \vc{v} - \frac{\vc{v} \cdot \vc{n}}{\vc{n} \cdot \vc{n}} \vc{n} \\ &= \frac{1}{f} \begin{pmatrix} fv_x - n_x n_x v_x - n_x n_y v_y - n_x n_z v_z\\ fv_y - n_y n_x v_x - n_y n_y v_y - n_y n_z v_z\\ fv_z - n_z n_x v_x - n_z n_y v_y - n_z n_z v_z \end{pmatrix}, \end{align} (8.38)
where $f = \ln{\vc{n}}^2 = \vc{n} \cdot \vc{n}$. Interestingly, this can be expressed as a matrix-vector multiplication
 \begin{align} \vc{q} &= \underbrace{ \frac{1}{f} \begin{pmatrix} f - n_x^2 & - n_x n_y & - n_x n_z \\ - n_y n_x & f - n_y^2 & - n_y n_z \\ - n_z n_x & - n_z n_y & f - n_z^2 \end{pmatrix} }_{\mx{A}} \underbrace{ \begin{pmatrix} v_x \\ v_y \\ v_z \end{pmatrix} }_{\vc{v}} = \mx{A}\vc{v}. \end{align} (8.39)
The dimension of the domain is 3, since we have three-dimensional vectors in $\R^3$ as input. Now since only vectors in the plane "survives", we know immediately that $\rank(\mx{A})=2$ and since we collapse one dimension, we have $\nullity(\mx{A})=1$.

$P$
$O$
$\vc{n}$
$\vc{v}$
$\proj{\vc{n}}{\vc{v}}$
$-\proj{\vc{n}}{\vc{v}}$
$Q$
$\vc{q}$
Interactive Illustration 8.4: This illustration will show how a point, $P$ (gray circle), is projected orthogonally down the a plane surface defined by a normal vector, $\vc{n}$, and a starting point, $O$, which is the origin. The point $P$ can be moved around in this illustration. Click/touch Forward to commence the illustration.
Interactive Illustration 8.4: Finally, the point $\hid{P}$ has been projected orthogonally to the plane and the projected point, $\hid{Q}$, is shown as a red circle. This, we have $\hid{\vc{q} = Q - O}$. Note that we derived a matrix, $\hid{\mx{A}}$, above that immediately calculates $\hid{\vc{q}}$ as $\hid{\vc{q} = \mx{A}\vc{v}}$. The points $\hid{\vc{v}}$ are three-dimensional, i.e., $\hid{\vc{v} \in \R^3}$. Note though that the projected points $\hid{\vc{q}}$ always reside in the light blue plane, that is, the set of all points $\hid{\vc{q}}$ is two-dimensional, which in turn implies that $\hid{\rank(\mx{A}) = 2}$. The nullity of the matrix is 1, i.e., $\hid{\nullity(\mx{A})=1}$, since we "remove" one dimension with the transform, $\hid{\mx{A}}$.
Now, let us explore the null space of $\mx{A}$. We know from Section 8.2 that nullity can be computed by performing Gaussian elimination on $\mx{A}\vc{x}=\vc{0}$. Without loss of generalization, we can assume that $\vc{n} = (0,0,1)$, i.e., $f=1$, and $S=O=(0,0,0)$. This results in
 $$\left( \begin{array}{rrr|r} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right),$$ (8.40)
that is, the result is already on row echelon form and since the last row has only zeroes, we have $\rank(\mx{A})=2$. We can set $p_z=t$, where $t\in\R$. This leaves the first two rows unaffected, which means that the null space is spanned by $(0,0,t)$, i.e., $\nullity(\mx{A})=1$. This makes sense since the normal is $\vc{n} = (0,0,1)$, and all vectors are collapsed by $\mx{A}$ to a plane $z=0$. The column space basis vectors are the first and second column vectors, i.e.,
 \begin{gather} \vc{b}_1 = \begin{pmatrix} 1\\ 0\\ 0 \end{pmatrix} \ \ \ \mathrm{and}\ \ \ \vc{b}_2 = \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix}. \end{gather} (8.41)
This means that the column space is the set of all vectors described by
 $$\vc{q} = u\vc{b}_1 + v\vc{b}_2 = \begin{pmatrix} u\\ v\\ 0 \end{pmatrix},$$ (8.42)
where $u\in\R$ and $v\in\R$, which also means that $\rank(\mx{A})=2$. Finally, we note that Theorem 8.8 states that $\rank(\mx{A}) + \nullity(\mx{A}) = n$, which indeed is true also in this case since $2+1=3$.

Example 8.10:
This is another example showing how to compute the rank, nullity, etc. We start with a $4\times 6$ matrix $\mx{A}$, which is
 $$\mx{A}= \left( \begin{array}{rrrrrr} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & -1 & 0 & -1 & 2 \\ 1 & 1 & 1 & 0 & 1 & 2 \\ \end{array} \right).$$ (8.43)
We will perform Gaussian elimination in order to get the matrix on row-echelon form. First, for row 2, 3, and 4, we take the top row minus the row itself, which generates
 $$\left( \begin{array}{rrrrrr} 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 2 & 1 & 2 & -1 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ \end{array} \right).$$ (8.44)
The next step is to take row 2 minus row 4 and plance in row 4, which gives us
 $$\left( \begin{array}{rrrrrr} 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 2 & 1 & 2 & -1 \\ 0 & 0 & 0 & 0 & 0 & 2 \\ \end{array} \right).$$ (8.45)
As a final step, we swap places of row 2 and 3, which results in a matrix on row echelon form, i.e.,
 $$\mx{R}= \left( \begin{array}{rrrrrr} 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 2 & 1 & 2 & -1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 2 \\ \end{array} \right),$$ (8.46)
and let us now use this in $\mx{R}\vc{x}=\vc{0}$. We immediately get $2 x_6 = 0$ from the bottom row, i.e., $x_6=0$. Using row 3, we get $x_4+x_6=0$, i.e., $x_4=0$ as well. Row 2 gives us $2x_3 + 0 + 2x_5 + 0 = 0$, i.e., $x_3+x_5=0$. Therefore, we set $x_5=t$, which gives us $x_3=-t$. The top row says $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = x_1+x_2 -t + 0 +t +0 =0$, i.e., $x_1+x_2=0$. This time, we set $x_2=s$, i.e, $x_1 = -s$. In total, the solution to the homogeneous system is $\mx{A}\vc{x}=\vc{0}$
 $$\vc{x}_h= \left( \begin{array}{r} -s \\ s \\ -t \\ 0 \\ t \\ 0 \end{array} \right) = s \underbrace{ \left( \begin{array}{r} -1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{array} \right)}_{\vc{z}^1} + t \underbrace{ \left( \begin{array}{r} 0 \\ 0 \\ -1 \\ 0 \\ 1 \\ 0 \end{array} \right)}_{\vc{z}^2}.$$ (8.47)
This means that $\nullity(\mx{A})=2$ since there are two variables ($s$ and $t$) in this expression. The null vectors are $\vc{z}^1$ and $\vc{z}^2$. Since $n=6$ and $\nullity(\mx{A})=2$, we have $\rank(\mx{A})= 6-2=4$. The row vectors spanning the row space are all the 4 row vectors of $\mx{R}$ but also all the row vectors of $\mx{A}$ since Gaussian elimination does not change row space. The index of the column vectors spanning the column space are identified in $\mx{R}$, i.e, column 1, 3, 4, and 6, since those have the first element on each respective row. Hence, the column vectors spanning the column space are the column vectors in $\mx{A}$ with column number 1, 3, 4, and 6. Note that $\mx{A}\vc{z}^1=\vc{0}$ and $\mx{A}\vc{z}^2=\vc{0}$ (try performing the matrix-vector multiplications) and finally, if we have a system $\mx{A}\vc{x}=\vc{b}$, then the solution will lie in the row space of $\mx{A}$.

In Chapter 7, different ways to compute the determinant of a square matrix were presented. Using minors (see Definition 7.8), one can also find the rank of a matrix, as the subsequent theorem describes.

Theorem 8.9:
The rank of a matrix $\mx{A}$ (of size $m\times n$) is the largest integer $r$ for which some $r\times r$-minor is $\neq 0$.

This proof is divided into two parts, namely showing that the rank of the matrix is at least $r$ and the second part shows that the rank is at most $r$, which together complete the proof.
$i)$ Let us call an $r\times r$ submatrix by $\mx{S}$ whose determinant, $d$, is $\neq 0$, i.e., $d=|\mx{S}|\neq 0$. As we know, such a minor must be obtained by crossing out $m-r$ rows and $n-r$ columns. Next, we form a matrix $\mx{B}$ consisting of the rows that were not crossed out, which then consists of these $r$ rows of $\mx{A}$. The matrix elements of $\mx{S}$ are also included in $\mx{B}$, i.e., the minor $d$ can also be obtained by further crossing some columns from $\mx{B}$, and since $d\neq 0$, the columns of $\mx{S}$ must be linearly independent. Since $\mx{S}$ is contained in $\mx{B}$ there are at least $r$ linearly independent column vectors in $\mx{B}$ and we come to the conclusion that the rank of $\mx{B}$ is at least $r$. However, $\mx{B}$ has only $r$ rows and therefore the rank must be exactly $r$ and the row vectors of $\mx{B}$ must be linearly independent. Therefore, $\mx{A}$ must also have at least $r$ linearly independent row vectors, i.e., $\rank(\mx{A})\geq r$.
$ii)$ The purpose of this step is to show that the rank of $\mx{A}$ is at most $r$. Let us assume that $\mx{A}$ has $t$ linearly independent rows. We create a matrix $\mx{C}$ consisting of these rows and this matrix must have rank $t$, which means there are $t$ linearly independent columns in $\mx{C}$ as well. Next, we take these $t$ linearly independent columns by crossing out the other ones. This results in a $t\times t$ matrix, whose determinant is $\neq 0$ since its columns are linearly independent. This minor is also a minor of $\mx{A}$. Hence, the rank of $\mx{A}$ cannot be $> r$, since there then need to more more than $r$ linearly independent rows in $\mx{A}$.
$\square$

As a consequence of Theorem 8.9 and Theorem 7.8, where the latter says that the inverse of a matrix only is defined if its determinant is non-zero, we see that if a square $n\times n$ matrix $\mx{A}$ is to be invertible, then we must have $\rank(\mx{A})=n$.

Example 8.11:
Assume we want to compute the rank of the following $4\times 4$ matrix,
 $$\mx{A} = \left( \begin{array}{rrrr} 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 2 & 1 & -2 \\ 1 & 2 & 2 & -1 \\ \end{array} \right).$$ (8.48)
The determinant of $\mx{A}$ is zero (this is left as an exercise) so the rank must be less than 4. Next, we calculate one of the $3\times 3$ minors, e.g.,
 $$D_{11} = \left| \begin{array}{rrr} 0 & 1 & 1 \\ 2 & 1 & -2 \\ 2 & 2 & -1 \\ \end{array} \right| = 0,$$ (8.49)
and since $D_{11}=0$, we do not gain any new knowledge and as it turns out, we also have $D_{12}=D_{13}=D_{14}=0$ as well. However, continuing to strike out the second row and the first column, we obtain
 $$D_{21} = \left| \begin{array}{rrr} 1 & 1 & 0 \\ 2 & 1 & -2 \\ 2 & 2 & -1 \\ \end{array} \right| = 1,$$ (8.50)
and since at least one of the $3\times 3$ minors is not zero (in this case, $D_{21} \neq 0$), we can conclude that $\rank(\mx{A})=3$, since we already know that the only $4\times 4$ determinant is 0, all due to Theorem 8.9.

Example 8.12: The Structure from Sound Problem
In Interactive Illustration 8.2, we studied the problem of determining both sound source positions and microphone positions from the measured sound. In this setting, it turns out that signal processing can be used to find so called time-difference-of-arrival measurements. To make the presentations slightly simpler we will present the same problem, for the case of so called time-of-arrival problems.

In the example we had $m=8$ microphones. Let $\vc{r}_i$, $i = 1, \dots, m$ be the column vector representations of the 3D positions of these eight microphones. Study the sound position at some of the time instances $t_1, \dots, t_n$, where we have chosen $n$ time instances of the sound recordings. Let $\vc{s}_j$, $j = 1, \dots, n$ be the spatial coordinates of these $n$ 3D positions at which the sounds were transmitted. Assume that we measure the difference in time $t_{ij}$ between the emitted and the received sound for each combination of a time instance $j$ and for each microphone $j$. After multiplying this with the speed of sound $v$, we obtain measured distances
 $$d_{ij} = v t_{ij} = {\ln{\mathbf{r}_i - \mathbf{s}_j}}.$$ (8.51)
The problem is now to calculate both $\vc{r}_i$ and $\vc{s}_j$ from the distance measurements $d_{ij}$.

By squaring the measurement equations (8.51),
 $$d_{ij}^2= ( \mathbf{r}_{i} - \mathbf{s}_{j} )^T ( \mathbf{r}_{i} - \mathbf{s}_{j} ) = \mathbf{r}_{i}^T\mathbf{r}_{i} + \mathbf{s}_{j} ^T\mathbf{s}_{j} - 2 \mathbf{r}_{i}^T \mathbf{s}_{j}$$ (8.52)
we obtain a set of $mn$ polynomial equations in the unknown.

Let the compaction matrix $\mathbf{B}$ be defined as
 $$\mathbf{B}= \begin{pmatrix} \frac{d_{22}^2 - d_{21}^2 - d_{12}^2 + d_{11}^2}{-2} &\dots& \frac{d_{2n}^2 - d_{21}^2 - d_{1n}^2 + d_{11}^2}{-2} \\ \vdots &\ddots& \vdots \\ \frac{d_{m2}^2 - d_{21}^2 - d_{12}^2 + d_{11}^2}{-2} &\dots& \frac{d_{2n}^2 - d_{21}^2 - d_{1n}^2 + d_{11}^2}{-2} \end{pmatrix}$$ (8.53)
then the rank of $\mathbf{B}$ is at most 3, which will be explained below.

Let
 $$\mathbf{q}_i = \left[ \begin{matrix} (\mathbf{r}_{i} - \mathbf{r}_1) \end{matrix} \right]$$ (8.54)
and
 $$\mathbf{t}_j = \left[ \begin{matrix} ( \mathbf{s}_{j} - \mathbf{s}_1) \end{matrix} \right]$$ (8.55)
as the relative vectors between the first receiver position and the rest and between the first sender position and the rest. Let these be the column vectors of matrices $\mathbf{R}$ and $\mathbf{S}$ respectively, so that
 $$\mathbf{R}= \left[ \begin{matrix} \mathbf{q}_2 \ldots \mathbf{q}_m \end{matrix} \right]$$ (8.56)
and
 $$\mathbf{S}= \left[ \begin{matrix} \mathbf{t}_2 \ldots \mathbf{t}_n \end{matrix} \right] .$$ (8.57)
In this way the $(m-1) (n-1)$ compaction matrix constraint can be written
 $$\mathbf{B} = \mathbf{R}^\T \mathbf{S},$$ (8.58)
Here we see that the matrix $\mathbf{R}^\T$ has three columns, so the rank can be at most 3. Similarily $\mathbf{S}$ has three rows so the rank can be at most 3. From Theorem 8.6, we see that the rank that is equal to or lower than the rank of $\mathbf{R}$ and that of $\mathbf{S}$. Thus the rank of $\mathbf{B}$ is at most 3.

In the last example, we found that a matrix $\mathbf{B}$, which can be formed from measurements, is related to the parameters that we seek by $\mathbf{B} = \mathbf{R}^\T \mathbf{S}$. How can we calculate $\mathbf{R}$ and $\mathbf{S}$ from $\mathbf{B}$? In other words, how can we factorize the matrix $\mathbf{B}$ and write it as a product of two factors $\mathbf{R}$ and $\mathbf{S}$? This is the topic of the Chapter 11, where we will study so called matrix factorizations. These are useful tools in many applications.

 Chapter 7: Determinants (previous) Chapter 9: Linear Mappings (next)


text:
GMAT Question of the Day - Daily to your Mailbox; hard ones only

 It is currently 13 Dec 2018, 21:43

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

## Events & Promotions

###### Events & Promotions in December
PrevNext
SuMoTuWeThFrSa
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345
Open Detailed Calendar
• ### GMATbuster's Weekly GMAT Quant Quiz, Tomorrow, Saturday at 9 AM PST

December 14, 2018

December 14, 2018

09:00 AM PST

10:00 AM PST

10 Questions will be posted on the forum and we will post a reply in this Topic with a link to each question. There are prizes for the winners.
• ### The winning strategy for 700+ on the GMAT

December 13, 2018

December 13, 2018

08:00 AM PST

09:00 AM PST

What people who reach the high 700's do differently? We're going to share insights, tips and strategies from data we collected on over 50,000 students who used examPAL.

# Is -7 < y < 10 ? (1) y > -6 (2) y < 0

Author Message
TAGS:

### Hide Tags

Math Expert
Joined: 02 Sep 2009
Posts: 51188
Is -7 < y < 10 ? (1) y > -6 (2) y < 0  [#permalink]

### Show Tags

11 Nov 2017, 06:55
00:00

Difficulty:

25% (medium)

Question Stats:

85% (00:46) correct 15% (00:45) wrong based on 55 sessions

### HideShow timer Statistics

Is -7 < y < 10 ?

(1) y > -6

(2) y < 0

_________________
Math Expert
Joined: 02 Aug 2009
Posts: 7106
Is -7 < y < 10 ? (1) y > -6 (2) y < 0  [#permalink]

### Show Tags

11 Nov 2017, 09:47
Bunuel wrote:
Is -7 < y < 10 ?

(1) y > -6

(2) y < 0

Is -7 < y < 10 ?

(1) y > -6
if y is 0 ... Yes
if y is 15...No
Insuff

(2) y < 0
if y is -5...Yes
If y is -10... ans is No
Insuff

combined
$$0>y>-6$$
this falls within the range -7 < y < 10 ..
so ans is YES always

suff
_________________

1) Absolute modulus : http://gmatclub.com/forum/absolute-modulus-a-better-understanding-210849.html#p1622372
2)Combination of similar and dissimilar things : http://gmatclub.com/forum/topic215915.html
3) effects of arithmetic operations : https://gmatclub.com/forum/effects-of-arithmetic-operations-on-fractions-269413.html

GMAT online Tutor

PS Forum Moderator
Joined: 25 Feb 2013
Posts: 1217
Location: India
GPA: 3.82
Re: Is -7 < y < 10 ? (1) y > -6 (2) y < 0  [#permalink]

### Show Tags

11 Nov 2017, 09:55
chetan2u wrote:
Bunuel wrote:
Is -7 < y < 10 ?

(1) y > -6

(2) y < 0

Is -7 < y < 10 ?

(1) y > -6
if y is 0 ... Yes
if y is 15...No
Insuff

(2) y < 0
if y is -5...Yes
If y is -10... ans is No
Insuff

combined
$$0<y<-6$$
this falls within the range -7 < y < 10 ..
so ans is YES always

suff

Hi chetan2u

Intern
Joined: 11 Nov 2017
Posts: 22
Location: India
Concentration: Finance, Technology
Schools: ISB '19 (D)
GMAT 1: 710 Q49 V38
GPA: 3.5
WE: Consulting (Consulting)
Re: Is -7 < y < 10 ? (1) y > -6 (2) y < 0  [#permalink]

### Show Tags

11 Nov 2017, 10:18
Is -7 < y < 10 ?

(1) y > -6

(2) y < 0

Statement 1 doesnt put an upper limit for the value of y, and hence, not sufficient.
Statement 2 means y can take any negative value.

Combining; -6<y<0, which is a subset of the question stem.
Manager
Joined: 22 May 2017
Posts: 88
GMAT 1: 580 Q41 V29
GMAT 2: 580 Q43 V27
Re: Is -7 < y < 10 ? (1) y > -6 (2) y < 0  [#permalink]

### Show Tags

12 Nov 2017, 09:29
chetan2u wrote:
Bunuel wrote:
Is -7 < y < 10 ?

(1) y > -6

(2) y < 0

Is -7 < y < 10 ?

(1) y > -6
if y is 0 ... Yes
if y is 15...No
Insuff

(2) y < 0
if y is -5...Yes
If y is -10... ans is No
Insuff

combined
$$0>y>-6$$
this falls within the range -7 < y < 10 ..
so ans is YES always

suff

So according to you, answer is c
Dont you feel answer should be E because this don't give the correct answer.
PS Forum Moderator
Joined: 25 Feb 2013
Posts: 1217
Location: India
GPA: 3.82
Re: Is -7 < y < 10 ? (1) y > -6 (2) y < 0  [#permalink]

### Show Tags

12 Nov 2017, 10:57
chetan2u wrote:
Bunuel wrote:
Is -7 < y < 10 ?

(1) y > -6

(2) y < 0

Is -7 < y < 10 ?

(1) y > -6
if y is 0 ... Yes
if y is 15...No
Insuff

(2) y < 0
if y is -5...Yes
If y is -10... ans is No
Insuff

combined
$$0>y>-6$$
this falls within the range -7 < y < 10 ..
so ans is YES always

suff

So according to you, answer is c
Dont you feel answer should be E because this don't give the correct answer.

this is a Yes / No question type so we only need either a Yes or a No and if we get both then the answer could be C

combining 1 & 2 we get $$-6<y<0$$. so all the values of $$y$$ in this range are between $$-7<y<10$$. We have a Yes here. So C is sufficient
Re: Is -7 < y < 10 ? (1) y > -6 (2) y < 0 &nbs [#permalink] 12 Nov 2017, 10:57
Display posts from previous: Sort by

format: plain


text:
This function provides easy plotting for mass, ratio and delta traces from IRMS dual inlet data. It can be called either directly with a set of iso_file objects, or with a data frame prepared for plotting dual inlet data (see iso_prepare_dual_inlet_plot_data).

iso_plot_dual_inlet_data(...)

# S3 method for iso_file_list
iso_plot_dual_inlet_data(
iso_files,
data = character(),
filter = NULL,
panel = data,
color = file_id,
linetype = NULL,
shape = type,
size = 2,
label = file_id,
...
)

# S3 method for data.frame
iso_plot_dual_inlet_data(
df,
panel = data,
color = file_id,
linetype = NULL,
shape = type,
size = 2,
label = file_id,
...
)

## Arguments

... additional parameters passed on to iso_plot_data collection of iso_file objects which masses, ratios and deltas to plot (e.g. c("44", "45", "45/44", "d45/44") - without the units), if omitted, all available masses, ratios, and delta values are plotted. Note that ratios should be calculated using iso_calculate_ratios and delta values should be calculated using iso_calculate_deltas prior to plotting. any filter condition to apply to the data beyond the masses/ratio/delta selection (param data). For details on the available data columns see iso_get_raw_data with parameters gather = TRUE and include_file_info = everything(). whether to panel the data by anything. If using a single parameter (e.g. panel = panel), will generate a facet_wrap. If using a formula (e.g. panel = panel ~ . or panel = file_id ~ panel), will generate a facet_grid. The default for this parameter is to panel via facet grid by the y variable name but only if multiple y columns are provided. Otherwise will not generate any facets. If additional facet parameters are desired, please leave use facet_wrap and facet_grid diretly. variable to use for color aesthetic for the plot or constant value for the point and line color variable to use for linetype aesthetic for the plot or constant value for the line type variable to use for shape aesthetic for the plot or constant vlaue for the point shape variable to use for size aesthetic for the plot or constant value for the points size this is primarily of use for turning the generated ggplots into interactive plots via ggplotly as the label will be rendered as an additional mousover label. a data frame of the dual inlet data prepared for plotting (see iso_prepare_dual_inlet_plot_data)

Other plot functions: iso_mark_calibration_range(), iso_mark_outliers(), iso_mark_value_range(), iso_mark_x_range(), iso_plot_continuous_flow_data(), iso_plot_data(), iso_plot_raw_data(), iso_plot_ref_peaks(), iso_plot_residuals(), iso_plot_scan_data(), iso_prepare_continuous_flow_plot_data(), iso_prepare_dual_inlet_plot_data(), iso_prepare_scan_plot_data()


text:
## Filters

Q&A - Ask Doubts and Get Answers
Q

# Find the value of the following expressions when x = - 1, (i) 2x - 7

Q. 3.     Find the value of the following expressions, when $x=-1$:

(i)  $2x-7$

Answers (1)
Views

$\\2x - 7 \\= 2 \times ( -1 ) - 7 \\= -2 - 7 \\= -9$

If x = -1 the value of 2x - 7 = -9

Exams
Articles
Questions


text:
# zbMATH — the first resource for mathematics

An asymptotic formula for the voltage potential in a perturbed $$\varepsilon$$-periodic composite medium containing misplaced inclusions of size $$\varepsilon$$. (English) Zbl 1105.35011
The authors consider a composite medium made of an array of inclusions $$\varepsilon$$-periodically disposed at the center of each $$\varepsilon$$-cell, except for some of them which are slightly misplaced. The goal of the paper is to describe the error between the potential $$u_{\varepsilon d}$$ of this perturbed problem and that $$u_{\varepsilon }$$ obtained for the problem with everywhere perfectly disposed inclusions. The authors indeed consider the elliptic problem $$-\text{ div}(a_{\varepsilon }(x)\nabla u_{\varepsilon })=f$$, posed in a smooth domain $$\Omega$$ of $$\mathbb{R}^{n}$$ with nonhomogeneous Neumann boundary conditions on $$\partial \Omega : a_{\varepsilon }\partial u_{\varepsilon }/\partial \nu =g$$ on $$\partial \Omega$$. They add the compatibility condition between $$f$$ and $$g$$ and the further condition $$\int_{\Omega }u_{\varepsilon }\,dx=0$$.
The main result proves that the difference between the two potentials in $$\Omega$$ (plus a term involving this difference on $$\partial \Omega$$) is of order $$\varepsilon ^{3}$$ with a first order involving the Green function associated to the homogenized problem and a polarization tensor built with the solution of local problems. The proof heavily relies on the properties of these Green functions.

##### MSC:
 35B27 Homogenization in context of PDEs; PDEs in media with periodic structure 35A08 Fundamental solutions to PDEs 35J25 Boundary value problems for second-order elliptic equations 74Q05 Homogenization in equilibrium problems of solid mechanics 82C05 Classical dynamic and nonequilibrium statistical mechanics (general)
Full Text:


text:
# Cryptographically secure p2p implementation of GG

This topic is 1860 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello,

I have a question about how to create a mutual p2p trust between two players of this game. We have this stratego-like board game with game pieces of various ranks. When a there is a challenge between two pieces (they go to the same square) the winner (higher rank) is determined by a third party. The opponent's game pieces are never revealed to the other player.

How would I make a p2p program that doesn't require a third party and doesn't reveal the game pieces?

Problems with some suggestions:

Mental Poker - no, because the cards are revealed at some point.
Homomorphic encryption - no, because this requires the same encryption key.
Yao's millionare problem - no, because the higher piece doesn't always win, there are exceptions (see Spy and Private in the wiki link below)

Edited by mudslinger

##### Share on other sites

How would I make a p2p program that doesn't require a third party and doesn't reveal the game pieces?

It is logically impossible to do so.
Someone needs to make a decision which piece is stronger.
That someone needs to know the strength of both pieces.
You only have the two players to choose from to decide "someone."
Ergo, at least one of the players needs to know the strength of both pieces.

You have two choices:
1) Introduce a neutral third party, not under control of the two players. Typically, this is why online games use game servers hosted by the game operator. For a strategy game, it's quite likely you can have thousands of games running at the same time on a single server.
2) Relax the design, such that one of the players' computers (or both) knows all the game pieces, but don't display it to the user. A player using a memory scanner can find out all the pieces, but a casual player will still have a good game.

##### Share on other sites

1) Introduce a neutral third party, not under control of the two players. Typically, this is why online games use game servers hosted by the game operator. For a strategy game, it's quite likely you can have thousands of games running at the same time on a single server.
2) Relax the design, such that one of the players' computers (or both) knows all the game pieces, but don't display it to the user. A player using a memory scanner can find out all the pieces, but a casual player will still have a good game.

This defeats the point of my question. I don't think it's entirely impossible. Yao's millionaire problem comes pretty close.

This isn't really for a game, it's more of a thought experiment.

EDIT: I believe the problem is Secure Multi-party Computation, I just don't know how to implement it exactly yet.

Edited by mudslinger

##### Share on other sites

Someone needs to make a decision which piece is stronger.
That someone needs to know the strength of both pieces.
You only have the two players to choose from to decide "someone."
Ergo, at least one of the players needs to know the strength of both pieces.

What part of my argument are you saying is incorrect?
In the end, a compare-and-branch needs to happen in a CPU to decide that A is stronger than B.
To do that, you need to know the relative strengths of the pieces.
To do that, you need to impart strength information to the deciding side -- if not absolute, then at least relative enough that the other end *may* end up knowing the exact strength.

You can make some bit of obscuration by using some kind of binary search. "Is your pieces stronger than X?" If no, and I know is my piece, or weaker than my piece, then I know that the decision is made, without knowing exactly what the other piece is -- just that it is at least strong enough for X. If I choose X to not necessarily be my particular piece strength, sometimes some information can be held back. But, other times, the exact information is necessarily needed, when piece A is exactly one quantum stronger than piece B.

##### Share on other sites

But it is possible to compare two values from different parties without revealing those two values.

http://www.proproco.co.uk/million.html

I believe I currently have a solution in my head.

EDIT: I plan to use the millionaire solution (link above) to compare pieces. To guard against players cheating the system by always sending a high piece, both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

It's rough, but it looks doable.

Edited by mudslinger

##### Share on other sites
As a simpler (and less secure) option to the millionaire solution, would be for Alice to send bob a table of 100 different units, and request that bob send back 100 booleans indicating if that unit would win the battle. Alice then picks out the vale for the actual unit there, and tells bob the result (and the system below detects lies later).
On average, there'll be 50 units on the list that match Alice's claimed outcome, so bob does know with a 1/50 chance what Alice's unit was... Alice also knows the strength of bob's unit, in that she knows the results for 100 hypothetical battles against it... Actually, maybe this isn't a good idea at all ;-/

both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

Some online card games work this way, and it should be extendable to any game with deterministic rules, as long as you're ok with deferring cheat detection until the very end of the game, when it's ok to reveal all the secrets. In a many-player game, if one player drops out half way through, there's no way to validate their actions (unless everyone gives their keys to a trusted 3rd party at the start).

##### Share on other sites

But it is possible to compare two values from different parties without revealing those two values.

http://www.proproco.co.uk/million.html

I believe I currently have a solution in my head.

EDIT: I plan to use the millionaire solution (link above) to compare pieces. To guard against players cheating the system by always sending a high piece, both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

It's rough, but it looks doable.

Yes, but the point hplus0603 was making is that there is always some unevitable amount of information leakage about the other player's piece simply by virtue of knowing the result of the comparison and the value of your own piece. In some cases, or if you don't have many pieces, this may often be enough to deduce the other player's piece. For example, using cards, if my card is a king and you still win, then I know you have an ace, no matter how much cryptography and obfuscation you throw at the problem. A fix would be to increase the number of different pieces, or perform the comparison less often. Another method is to change the number of pieces dynamically, but this doesn't make for a very enjoyable game since the comparison is no longer consistent with what people would expect. If this caveat is unacceptable to you, your problem has no solution.

Otherwise, if this is fine (and hopefully it is) then Yao's approach seems doable since you probably don't have that many pieces. Now as for cheating, your solution works if the initial state + the movement information received by each player is enough to derive the game's state at any turn. You could also send the encrypted game state every turn with no information leakage for faster failure response (1 turn) but perhaps it is not worth it. Make sure to implement a commitment scheme as well so that a player can't "change his mind" on his game state once the keys are revealed (by revealing a fake key which decrypts to what he wants - not likely to succeed in practice but it can be done depending on your encryption scheme and the complexity of the game state).

##### Share on other sites

...

if this is fine then Yao's approach seems doable since you probably don't have that many pieces.

...

your solution works if the initial state + the movement information received by each player is enough to derive the game's state at any turn.

...

a player can't "change his mind" on his game state once the keys are revealed (by revealing a fake key which decrypts to what he wants - not likely to succeed in practice

...

I thought of these, it is a yes on all three points. It is the nature of the game that the strength of a piece is partially revealed after a challenge (e.g. opponent's piece won, it's stronger than mine).

Edited by mudslinger

##### Share on other sites

Yes, but the point hplus0603 was making is that there is always some unevitable amount of information leakage about the other player's piece simply by virtue of knowing the result of the comparison and the value of your own piece.

I believe that is by design in such games. This partial information is what the player uses to formulate their plan.

Just a thought, if you could impose a strict weak ordering on the ranks, I believe you can have a simple protocol to resolve the combat. Conceptually, each peer starts at the lowest value piece and asks if the other peer can beat it using their actual piece. If not, the peer asks if the next highest rank can beat it. And so on, stopping as soon as one player reveals they can beat that particular value. No more information is leaked than necessary.

For example, player A has a middling piece (e.g. "Lt. Colonel") but player B has a highly ranked piece (e.g. "Major General"). The protocol would be like so:

A -> B: Can you beat a flag: yes
B -> A: Can you beat a flag: yes

A -> B: Can you beat a spy: yes
B -> A: Can you beat a spy: yes

A -> B: Can you beat a private: yes
B -> A: Can you beat a private: yes

A -> B: Can you beat a sergeant: yes
B -> A: Can you beat a sergeant: yes

// ...

A -> B: Can you beat a major: yes
B -> A: Can you beat a major: yes

A -> B: Can you beat a Lt. Colonel: no
B -> A: Can you beat a Lt. Colonel: yes

Thus both players conclude that player B wins, without B revealing the exact value of the winning piece.

Unfortunately, the game you linked to does not appear to have this property, in particular due to the "Spy". Forcing the game logic to fit a strict weak ordering would probably also reduce some of the "strategy", by eliminating such interesting ranks; potentially making the game considerably less fun.

Maybe there is a clever way to handle such a case, but I cannot see it. The protocol would have be modified such that if a spy would lose, the spying peer can "reveal" the spy to allow the protocol to continue. Such an implementation would reduce the information being leaked to "just" spies (though they are quite a notable piece).

For example, player A has a their officer level piece (e.g. "Sergeant") and player B has a spy. The protocol would be like so:

A -> B: Can you beat a flag: yes
B -> A: Can you beat a flag: yes

A -> B: Can you beat a spy: yes
B -> A: Can you beat a spy: no, but I am a spy

A -> B: Can you beat a private: yes
B -> A: Can you beat a private: no, but I am a spy

A -> B: Can you beat a sergeant: no
B -> A: Can you beat a sergeant: yes

So the sergeant would be removed.

Maybe some of the uncertainty could be reclaimed by adding more special pieces to the mix, though the protocol itself might break down entirely too. Just thinking out loud, I may have made a mistake in my reasoning.

##### Share on other sites

That's very open to cheating. I can pretend to have another piece, and thus get a good read on what your piece is.
The same holds for the Millionaire's problem -- if I can force a comparison with an arbitrary value, I can gain information.

If it were me, I wouldn't worry about players who are attaching to my game and reading that level of game state out of RAM.
If you need to play this for money or in tournament play, play should be on controlled hardware (e g in a physical location.)
For casual play, someone cheating online will just end up getting matched against other players also cheating online if your matchmaking is good enough :-)

• 16
• 9
• 13
• 41
• 15


text:
## Presentation of power-ordered sets

• Power-ordered sets are not always lattices. In the case of distributive lattices we give a description by disjoint of chains. Finite power-ordered sets have a polarity. We introduct the leveled lattices and show examples with trivial tolerance. Finally we give a list of Hasse diagrams of power-ordered sets.

$Rev: 13581$


text:
# AP 7th Maths Mock Test 2021 For Chapter – 2 : ” Fractions , Decimals And Rational Numbers ” Online Practice Test

1. What is the sum of , and 1 ?
2. What is the difference of and ?
3. What is the product of 1 , 3 and ?
4. What should be added to 3 to get 3 ?
5. The sum of two rational numbers is - 8 . If one of the numbers is , what is the other ?
6. What should be added to to get ?
7. What is the value of [2 - - ] ?
8. What is the value of x if = ?
9. What is the value of -$\times$35 ?
10. Match the following
1. =                             ( ) a.
2. 2 =                       ( ) b. 20
3. 0.2100 =                 ( ) c. 2

11. The value of 0.1 51.7 is
12. Evaluate 251.2 =
13. 4 - of 6 is
14. 235.4100 =
15. of the fruit was eaten by Goutham , the rest part of the fruit is
16. Match the following

17. Match the following
1.          ( ) a.
2.    ( ) b.
3. -              ( ) a.
4. 4 - 2         ( ) a.
18. Match the following
1. 1 cm ( ) a. 1000 g
2. 1 kg  ( ) b. 100 cm
3. 1 m   ( ) c. 10 mm
19. is a .................... fraction
20. is a .................... fraction
21. 2 is a .................... fraction
22. Every natural number can be written as ...................... fraction
23. is a ...................... fraction
24. is an improper fraction means ....................................................
25. Each proper fraction is
26. Which of the following is incorrect ?
27. In the following , which fraction is not equivalent to ?
28. 3 + 5 =
29. The shaded area in a figure represents then the unshaded are represents .........................
30. in its simplest form is
31. In a cake shyam ate part and he distributed the remaining equally to 5 members . Then each member gets ................... part of the cake
32. Which of the following is true with respect to and ?
33. What is the product of a fractional number and its reciprocal ?
34. If 4 = what is the value of x ?
35. How many one - fourths need to be added to 3 to make 6 ?
36. Between which 2 numbers does lie ?
37. Which of the following statements is true ?
38. What result will be obtained when the sum of and is divided by their difference ?
39. Arrange the following in ascending order , ,
40. Among 2 , 1.37 , 1.07 , - 1.49 which is greater ?
41. Which of the following is not true ?
42. Arrange the decimals in ascending order : 2.05 , 4 , 0.75, - 4.56
43. If is a proper fraction , then is a .......................... fraction
44. If and are both improper fractions then we must have
45. a , x are positive integers then , , are in
46. 3 =
47. Which of the following is incorrect ?
48. Indian cricket team won 4 more matches than it lost with Newzealand . If it won of its matches , how many matches did India play ?
49. Find the additive inverse of -[ + ]
50. Which of the following is incorrect ?
51. How many pieces each of length 3 m can be cut from a rope of length 60 m ?
52. The equivalent fraction of with numerator 24 is
53. Ramu read of a book . He finds that there are still 80 pages left to be read . What is the total number of pages in the book ?
54. Vanaja eats one full bar of chocolates , then she divides another one into 5 equal parts and eats 3 of them . What is the total number of chocolates that she has eaten ?
55. The product of two numbers is 15 . If one of the numbers is 6 , what is the other number ?
56. A badminton player won 7 games and lost 3 . What fraction of the games did he lost ?
57. Vasu had of a cake . He ate of it . What part of the cake did he eat ?
58. A bus is moving at an average speed of 56km/hr . How much distance it cover in 3 hour ?
59. The cost of 4 meters of cloth is ₹98 what is the cost of cloth per meter ?
60. A bus can cover 21.25 km in half an hour . How much distance it cover in 12 hours ?
61. Madhavi purchased a notebook for ₹27.75 , a pencil for ₹4.25 and a pen ₹26.45. She give a ₹100 note to the shopkeeper . What amount did she get back ?
62. 1 meter of cloth costs ₹52.25. what is the cost of 9.5 meters of this cloth ?
63. Subash bought 17.5 litres of Mustard oil for ₹1550.50 , what is the cost per one litre ?
64. In a class of 45 students of the total number of students are girls . How many students of the class are boys ?
65. A car runs 12 km using 1 litre of petrol , how much distance will it cover using 2.5 litres of petrol ?
66. Sugar is sold at ₹17 per kg . Find the cost of 8 kg of sugar
67. A cartoon contains 40 boxes of nails and each box weights 3 kg . How much would a cartoon of nails weigh ?
68. In which of the following does the shaded part represents one fourth of its whole ?
69. Which of the following is an improper fraction ?
70. What does the shaded part of the following strip represent ?
71. Find the perimeter of the figure
72. Express in fraction form ..................
73. Pictorial representation of 3 =
74. Representation of of 16 is
75. Which is bigger among or ?
76. The number of the form , where a and b are whole numbers and b0 are called
77. A fraction whose denominator is greater than its numerator is called
78. A fraction whose denominator is less than or equal to its numerator is called
79. The sum of a whole number and a proper fraction is called
80. Every proper fraction is of value
81. Every improper fraction is of value
82. Fractions having same denominator are called
83. Reciprocal of is
84. Product of two fractions =
85. All positive proper fractions lie between
86. Which of the following is not a equivalent fraction of
87. Which of the following is a equivalent fraction of
88. 52 =
89. 51 =
90. 41 =
91. of the circles in box
92. A truck runs 8 km using 1 litre of petrol . How much distance will it cover using 10 litres of petrol ?
93. Rani walks 1 meters in 1 second . How much distance will he walk in 15 minutes ? Rani walks 1 meters in 1 second
94. The reciprocal of a proper fraction be a
95. The reciprocal of is
96. Deepak can paint of a house in one day . if he continues working at this rate , how many days will he take to paint the whole house ?
97. Area of rectangle with length 6.2 cm and breadth 4 cm is ............. sq.cm
98. A motor bike covers a distance of 62.5 km consuming one litre of petrol . How much distance does it cover for 10 litres of petrol ?
99. A side of regular polygon is 3.5 cm  in length . The perimeter of the polygon is 17.5 cm . How many sides does the polygon have ?
100. A rainfall of 0.896 cm was recorded in 7 hours , what was the average amount of rain per hour ?


text:
Specific isomorphism of $\mathbb{R}^2$ as an $\mathbb{R}[X]$-module

I am reading some algebra notes by <NAME>, who offers the following example.

View $V = \mathbb{R}^2$ as an $\mathbb{R}[X]$-module where $X$ acts as the matrix $\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$. Note that $\{e_2, X(e_2)\}$ is a basis for $V$ and that $(X^2 - 2X + 1)(e_2) = 0$.

Therefore, $V \cong \mathbb{R}[X] / (X^2 - 2X + 1)$.

My linear algebra is rusty, so I don't see how the last line follows exactly. Any help please?

Define an $\mathbb R$-linear transformation $\phi:\mathbb R[X] \rightarrow V$ by
$$\phi(f) = f(T)e_2$$
This is also a homomorphism of $\mathbb R[X]$-modules. It is surjective, so $\phi$ induces an isomorphism of $\mathbb R[X]$-modules $\mathbb R[X]/I \rightarrow V$, where $I$ is the kernel of $\phi$.
You then need to check that $I = (X^2 - 2X+1)$.


text:
# Rate of reaction

1. Sep 12, 2011

### quietrain

consider

3A + 5B ----> 4C + 2D

if this is an elementary process

the rate of reaction is given as

r = k [A]3 [ B ]5 , where k is rate constant, [x] are concentrations

so my question is , why is the rate of production of A = 3 times the rate of reaction?

since the rate of reaction has already taken into account the 3 moles of A, shouldn't the rate of production of A = rate of reaction ?

thanks!

2. Sep 16, 2011

anyone?


text:
### Night_Lord's blog

By Night_Lord, history, 7 months ago,

Hello,need idea for this problem from SPOJ SEQ — Recursive Sequence . I am really new in matrix exponentiation learning.Here I learnt from this blog T matrix for the test case-

3
1 2 3
4 5 6
6

is T=

0 1 0
0 0 1
6 5 4

Then I multiply T with Identity matrix I.For me the answer should store in I[n-1][n-1].But maybe here I am missing something which I clearly missing completly.I searched in google and github but could not get a satisfactory answer.

my code

• 0

 » 6 months ago, # |   0 .
•  » » 7 weeks ago, # ^ |   0 you can check out my AC code https://ideone.com/Xi8MsX


text:
# Chapter 10 - Exponents and Radicals - 10.2 Rational Numbers as Exponents - 10.2 Exercise Set - Page 642: 114

$\sqrt[4]{ 2^{}x^{}y^2}$

#### Work Step by Step

Using $a^{-x}=\dfrac{1}{a^x}$ or $\dfrac{1}{a^{-x}}=a^x,$ then \begin{array}{l}\require{cancel} \sqrt[4]{\sqrt[3]{8x^3y^6}} \\\\= \sqrt[4]{ \left( 8x^3y^6 \right)^{1/3}} \\\\= \left( \left( 8x^3y^6 \right)^{1/3} \right)^{1/4} .\end{array} Using the Product Rule of the laws of exponents which is given by $x^m\cdot x^n=x^{m+n},$ the expression above is equivalent to \begin{array}{l}\require{cancel} \left( \left( 8x^3y^6 \right)^{1/3} \right)^{1/4} \\\\= \left( 8x^3y^6 \right)^{\frac{1}{3}\cdot\frac{1}{4}} \\\\= \left( 8x^3y^6 \right)^{\frac{1}{12}} \\\\= \left( 2^3x^3y^6 \right)^{\frac{1}{12}} .\end{array} Using the extended Power Rule of the laws of exponents which is given by $\left( x^my^n \right)^p=x^{mp}y^{np},$ the expression above is equivalent to \begin{array}{l}\require{cancel} \left( 2^3x^3y^6 \right)^{\frac{1}{12}} \\\\= 2^{3\cdot\frac{1}{12}}x^{3\cdot\frac{1}{12}}y^{6\cdot\frac{1}{12}} \\\\= 2^{\frac{1}{4}}x^{\cdot\frac{1}{4}}y^{\frac{2}{4}} .\end{array} Using $x^{m/n}=\sqrt[n]{x^m}=\left(\sqrt[n]{x} \right)^m,$ then \begin{array}{l}\require{cancel} 2^{\frac{1}{4}}x^{\cdot\frac{1}{4}}y^{\frac{2}{4}} \\\\= \sqrt[4]{ 2^{1}x^{1}y^2} \\\\= \sqrt[4]{ 2^{}x^{}y^2} .\end{array}

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
MathSciNet bibliographic data MR1562454 Contributed Item <NAME>.; Some involutorial line transformations interpreted as points of \$V\sb 2\$$V\sb 2$ of \$S\sb 5\$$S\sb 5$. Bull. Amer. Math. Soc. 38 (1932), no. 8, 533–540. Article

For users without a MathSciNet license , Relay Station allows linking from MR numbers in online mathematical literature directly to electronic journals and original articles. Subscribers receive the added value of full MathSciNet reviews.


text:
# Order and degree of a differential equation

Here is a question in my book

Find the order and degree of the differential equation $$y=1+\frac{dy}{dx}+\frac{1}{2!}{\left(\frac{dy}{dx}\right)}^2+\frac{1}{3!}{\left(\frac{dy}{dx}\right)}^3+\cdots$$

At first sight we can conclude that the order is $$1$$ and the degree is undefined as as the power of $$\frac{dy}{dx}$$ continues to increase and has no limit.However my book gives the following solution

Rewrite the DE as $$y=\exp\left({\frac{dy}{dx}}\right)$$ $$\implies \frac{dy}{dx}=\ln y$$ whose order and degree is 1 .

Now ,I completely agree with this solution however I find it rather counterintuitive to my first line of thought .If the book is correct how can it be justified to prove my intuition was wrong?

• Comments are not for extended discussion; this conversation has been moved to chat. Mar 2, 2021 at 13:42

The book is indeed incorrect, when you do such modifications on the equation, the order and degree changes. You must read the order and degree of the equation you are given without any simplification. To illustrate what I mean, suppose I give you:

$$y' =y$$

I could square the above and get:

$$(y')^2 = y^2$$

Now, look at the two equations you may see first equation was first degree and second is second degree.

However, in case of JEE and board exams (Indian syllabus stuff) , usually they want you to simplify before saying degree or order (this is actually wrong though)

Related

• I completely agree. On a further note, the immediate equation after simplification of the infinite sum is $y=e^{y'}$. The degree of this equation is infinite/undefined. Though further manipulation results in $y'=\ln y$, these 2 equations are not equivalent even though they have the same solution set. This is exactly what buraian wants to emphasize with his $y'=y$ example. Feb 21, 2021 at 14:45
• Nice example of squaring both sides and saying the degree changes ,it certainly illustrates your point very well !! (+1) Feb 21, 2021 at 14:48

Your intuition about the order of given ODE is correct as writing the RHS into closed form function never changes it. But the degree of an ODE is a parameter which is something vague to talk about as one can always disturb it just by squaring both sides.

Though if you constraint yourself to the topic linear ODE (which seems to be true as per your syllabus of JEE) then $$y=1+y'+\frac{y'^2}{2!}+....$$ is a non-linear ODE which on linearization gives you the linear version : $$y'=\log_e y$$ has degree $$1$$ (if you still want to define this parameter).


text:
• ### 13th International Conference on Elastic and Diffractive Scattering (Blois Workshop) - Moving Forward into the LHC Era(1002.3527)

Proceedings of the 13th International Conference on Elastic and Diffractive Scattering (Blois Workshop) - Moving Forward into the LHC Era
• ### 12th International Conference on Elastic and Diffractive Scattering (Blois Workshop) - Forward Physics and QCD(0712.3633)

June 5, 2008 hep-ph
Proceedings of the 12th International Conference on Elastic and Diffractive Scattering (Blois Workshop) - Forward Physics and QCD
• ### Gluon shadowing in the Glauber-Gribov model at HERA(0705.1596)

Sept. 6, 2007 hep-ph
We calculate shadowing using new data on the gluon density of the Pomeron recently measured with high precision at HERA. The calculations are made in a Glauber-Gribov framework and Pomeron tree-diagrams are summed up within a unitarity-conserving procedure. The total cross section of $\vphot A$ interaction is then found in a parameter-free description, employing gluon diffractive and inclusive distribution functions as input. A strong shadowing effect is obtained, in good agreement with several other models. Impact parameter dependence of gluon shadowing is also presented.
• ### pi0 Fixed pT suppression and elliptic flow at LHC(0706.3315)

June 22, 2007 hep-ph
Using a final state interaction model which describes the data on these two observables, at RHIC, we make predictions at the LHC -- using the same cross-section and pT-shift. The increase in the medium density between these two energies (by a factor close to three) produces an increase of the fixed pT pi0 suppression by a factor 2 at large pT and of v2 by a factor 1.5.
• ### J/psi suppression at SPS and RHIC in the comovers approach(nucl-th/0104004)

April 2, 2001 nucl-th
The NA50 collaboration data on the $J/\psi$ suppression are compared with the results obtained in a comovers approach based on the Dual Parton Model (DPM). Predictions for the $J/\psi$ suppression versus the charged multiplicity - measured in the rapidity region of the dimuon trigger - are given for SPS and RHIC energies.
• ### Review of Theory Talks at Xxix International Symposium on Multiparticle Dynamics(hep-ph/9912360)

Dec. 15, 1999 hep-ph
A short summary of main results of theoretical talks presented at XXIX International Symposium on Multiparticle Dynamics is given.
• ### Gribov Theory of Nuclear Interactions and Particle Densities at Future Heavy-Ion Colliders(hep-ph/9903244)

March 3, 1999 hep-ph
Gribov approach to high-energy interactions of hadrons and nuclei is reviewed and applied to calculation of particle production in heavy-ions collisions. It is pointed out that the AGK (Abramovsky, Gribov, Kancheli) cutting rules is a powerful tool to investigate particle spectra in these processes. It leads, in the Glauber approximation, to a simple formula for the density of hadrons produced in the central rapidity region in nucleus-nucleus interactions. An estimate of this density for RHIC and LHC is presented and compared with results of Monte-Carlo calculations. It is shown that the Glauber approximation substantially overestimate particle densities compared to the results of the complete Gribov theory. This is due to extra shadowing in the system, related to large mass diffraction which leads to a strong decrease of particle densities at mid rapidities. Our method of calculation of these effects has been applied to the problem of shadowing of nuclear structure functions and a good agreement with experimental data has been obtained.
• ### $J/\Psi$ and $\Psi '$ Suppression in Heavy Ion Collisions(hep-ph/9607265)

July 9, 1996 hep-ph
We study the combined effect of nuclear absorption and final state interaction with co-moving hadrons on the $J/\Psi$ and $\Psi '$ suppression in proton-nucleus and nucleus-nucleus collisions. We show that reasonable description of the experimental data can be achieved with theoretically meaningful values of the cross-sections involved and without introducing any dicontinuity in the $J/\Psi$ or $\Psi '$ survival probabilities.
• ### Strange Baryon Production in Heavy Ion Collisions(hep-ph/9507250)

July 7, 1995 hep-ph
The rapidity distribution of $\Lambda$ and $\bar{\Lambda}$ produced in nucleus-nucleus collisions at CERN energies is studied in the framework of an independent string model - with quark-antiquark as well as diquark-antidiquark pairs in the nucleon sea. It is shown that, besides the $\Lambda$-$\bar{\Lambda}$ pair production resulting from the fragmentation of sea diquarks, final state interactions of co-moving secondaries $\pi + N \to K + \Lambda$ and $\pi + \bar{N} \to K + \bar{\Lambda}$ are needed in order to reproduce the data. Predictions for $Pb$-$Pb$ collisions are presented.
• ### Hard Diffraction at HERA and the Gluonic Content of the Pomeron(hep-ph/9506454)

June 29, 1995 hep-ph
We show that the previously introduced CKMT model, based on conventional Regge theory, gives a good description of the HERA data on the structure function F_2^D for large rapidity gap (diffractive) events. These data allow, not only to determine the valence and sea quark content of the Pomeron, but also, through their Q^2 dependence, give information on its gluonic content. Using DGLAP evolution, we find that the gluon distribution in the Pomeron is very hard and the gluons carry more momentum than the quarks. This indicates that the Pomeron, unlike ordinary hadrons, is a mostly gluonic object. With our definition of the Pomeron flux factor the total momentum carried by quarks and gluons turns out to be 0.3-0.4 - strongly violating the momentum sum rule.
• ### Diffractive Dissociation in Deep Inelastic Scattering at HERA(hep-ph/9407372)

July 26, 1994 hep-ph
The diffraction dissociation of virtual photons is considered in the framework of conventional Regge theory. It is shown that the recent HERA data on large rapidity gap events can be successfully described in terms of the Pomeron structure function. Using Regge factorization, the latter can be related to the deuteron structure function. The parameters which relate these two structure functions are determined from soft hadronic diffraction data. The size of the shadowing corrections at low x and large Q**2 is also obtained.
• ### Structure functions and low x physics(hep-ph/9405338)

May 20, 1994 hep-ph
In the framework of conventional Regge theory we present a common description of total photon-proton cross-section and proton structure functions in the region $0 \leq Q^2 \leq 5 \ {\rm GeV}^2$. Using it as an initial condition in the perturbative QCD evolution equation, we describe structure functions at any $Q^2$ and $x$ - including the small $x$ region explored at HERA.