Linear Algebra (for IEM) 2021/22

Prof. Dr. Stephan Trenn

Exercise sheet 2
In-class-exercise T4
You travel to a foreign island, whose inhabitants use a strange language consisting of words build
only from the three letters M, I and U. The inhabitants are very sensitive to an abuse of their
language and will kill everyone using wrong words. A friend of you told you the rules when a word
is correct:
(R1) MI is a correct word
(R2) To every correct word ending with I one letter U can be added at the end to obtain another
correct word.
(R3) If a correct word of length n starts with M the last n − 1 letters can be copied at the end of
the word to obtain another correct word (of length 2n − 1).
(R4) In a correct word any three consecutive I can be replaced by one letter U.
(R5) In a correct word any two consecutive U can be removed.
(R6) Only words produced by the above rules are correct.
After some thinking you show the inhabitants the word MUIIU. Unfortunately, they have never
seen this word and are threatening to kill you, unless you prove to them that MUIIU is indeed
correct, so show which rules (in which order) you can use to arrive at the word MUIIU. Later
this evening you hear about an ancient saga which says that showing the word MU to the leader
of the island at noon of mid-summer will make you immortal from any possible illness, why?
Solution:
The word MUIIU is indeed correct as the following derivation starting with the correct word MI (established by
(R1)) shows:
(R3) (R3) (R4) (R2) (R3) (R5)
MI → MII → MIIII → MUI → MUIU → MUIUUIU → MUIIU
The word MU is not correct, because the number of I’s in each word produced by rules (R1)-(R5) is not divisible by
three, but MU contains zero I’s (which is divisible by three), so by (R6) MU cannot be correct (because it cannot
by produced by the rules (R1)-(R5)). This can be seen by induction: Clearly, the number of I in MI is one and
hence not divisible by three. Rules (R2) and (R5) do not change the number of I’s. Rule (R3) doubles the number
of I’s in a correct word, however if a number of I’s is not divisible by three then also two-times that number is not
divisible by three, so (R3) also can produce correct words where the number of I’s is divisible by three from correct
words where the number of I’s is not divisible by three. Finally, rule (R4) removes from a correct three I’s, which
doesn’t change the divisibility with respect to three.

The purpose of this exercise is to make students familiar with formal reasoning (first part), in particular, one
can “prove” “Theorems” just on a symbolic level without understanding what the Theorem actually means. This
is quite similar to what will happen when introducing vector spaces later in an axiomatic way and then proving
statements like (−1) · v = −v which seem totally obvious but need a formal proof (where one forgets about the
meaning of the symbols).
The second part shows that sometimes it is necessary to “step out of” the formal system to proof something, it is
not possible to proof that MU is not a Theorem just with the rules (R1)-(R6) because we have no rules how to
“produce” incorrect words. In fact, without (R6) we cannot even conclude that MU is really incorrect, because we
then would have no rule about incorrect words. This indicates that formal systems can be incomplete. This again
is important when introducing vector spaces axiomatic, because if we leave away any of the defining properties, we
would not be able to show some desired property. For example, without the rule v + 0 = v it is not possible to
show 0 · v = 0.

In-class-exercise T5
A matrix has many reduced row forms. Can you argue that the number of zero rows is the same
in every RRF?
For a matrix M define the ronk to be the number of non-zero elements in a reduced row form of
the matrix. Prove that there exists a matrix (call it A) such that it has two different RRF’s A1 , A2
with ronkA1 = 2, ronkA2 = 3.

This shows that the ronk is not unique. So we can not talk about the ronk of a matrix, in contrast
to the rank of a matrix which is unique and well-defined.

1/2 compiled: 22/11/2021

Solution:
Consider the matrices    
1 2 1 0
A1 = , A2 =
0 2 0 2
and set A = A1 .

In-class-exercise T6
Describe the solution space of the following augmented coefficient matrix.
  
1 3 0  5
0 2 1  6

Can you give a geometric interpretation of this solution space? Next, do the same for this matrix
  
1 3 2  5
.
2 6 4  6

Can you use your intuition from above to give a geometric interpretation of this solution space?

The remaining time of the tutorial can be used to discuss the Sowiso-exercises of Lecture 2 & 3.

Each of the inclass-exercises are supposed to be solved during the tutorials within about 15 minutes. This can be
done in groups of up to four students and the TA will assist you in finding a solution. Afterwards the solution will
be presented by one student, the TA will moderate this presentation and the following discussion.
Attention: Each student has to present at least one solution (also possible in the computer tutorials) during the
8 weeks of the course. You can prepare the inclass-exercise also before the tutorial and contact the TA if you want
to present the solution.

2/2 compiled: 22/11/2021