Scribd
Upload
9 views2 pages

Language Rules and Matrix Exercises

The document contains exercises from a linear algebra course. It includes word problems involving rules to generate words in a made-up language and matrix problems involving reduced row echelon form and solution spaces. The purpose is to familiarize students with formal reasoning and proving properties without meaning, as well as showing that formal systems can be incomplete. Students are expected to solve the exercises in groups during tutorials with assistance from teaching assistants.

Uploaded by

Stefanos van Dijk
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

Language Rules and Matrix Exercises

The document contains exercises from a linear algebra course. It includes word problems involving rules to generate words in a made-up language and matrix problems involving reduced row echelon form and solution spaces. The purpose is to familiarize students with formal reasoning and proving properties without meaning, as well as showing that formal systems can be incomplete. Students are expected to solve the exercises in groups during tutorials with assistance from teaching assistants.

Uploaded by

Stefanos van Dijk
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Linear Algebra (for IEM) 2021/22

Prof. Dr. Stephan Trenn


Stefanos van Dijk

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


Linear Algebra (for IEM) 2021/22
Prof. Dr. Stephan Trenn
Stefanos van Dijk

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

Common questions

Powered by AI

The word "MUIIU" is correct based on a sequence of transformations starting from "MI": MI (R3) →MII (R3) →MIIII (R4) →MUI (R2) →MUIU (R3) →MUIUUIU (R5) →MUIIU . This process of derivations using specific rules demonstrates the nature of formal reasoning where symbolic manipulation can prove the validity of statements (words) irrespective of actual understanding of their meaning, akin to the formal axiomatic proofs in vector spaces .

A matrix cannot have multiple reduced row forms with different numbers of zero rows. The number of zero rows in any reduced row echelon form of the same matrix is always the same. This pertains to the concept of rank, which is the number of non-zero rows in any reduced row form and is a unique attribute of a matrix .

Stepping outside the formal system is necessary to account for the limitations inherent within predefined rules that lack mechanisms for identifying incorrect outputs. In the case of 'MU', formal rules (R1)-(R5) do not create a framework for generating this particular word or others deemed incorrect. A real-world analogy is mathematical proofs that require assumptions or previously established theories outside the current scope .

The solution space of an augmented matrix can be interpreted geometrically as a subspace in n-dimensional space where n corresponds to the number of variables. For instance, a 2x2 matrix typically corresponds to a line in 2D space, whereas a 3x3 matrix might represent a plane in 3D space. This type of interpretation aids in building intuition in linear algebra by relating abstract solutions to visual, spatial concepts .

Proving 'MU' as invalid highlights that formal systems can be incomplete because formal reasoning within given rules (R1)-(R6) alone cannot establish MU's incorrectness. It requires stepping outside to apply a broader understanding, like the count of 'I's. This reflects similar limitations in axiomatic systems in math (e.g., vector spaces), where certain properties or theorems can't be proven without specific axioms or stepping beyond the confines of current axioms .

RRFs of a matrix can differ in the placement of non-zero elements, and hence, while the number of non-zero rows (rank) remains constant, the "ronk" may differ. This is because "ronk" refers to the total count of non-zero elements rather than non-zero rows. For example, matrix A has two different RRFs A1 and A2 where the number of non-zero elements, termed as "ronk", differs (ronkA1 = 2, ronkA2 = 3). Unlike the rank, which is well-defined and invariant among all RRFs, "ronk" is not unique due to different possible distributions of zeros and non-zeros in RRFs.

Formal proofs are crucial for establishing even seemingly obvious truths because they ensure rigor and generalizability beyond intuition. An example is proving identities like (-1)·v = -v in vector spaces, which seems obvious but needs formal axiomatic verification to remove subjective interpretation or unfounded assumptions. This parallels the exercise in proving word validity using specific rules without presupposed meanings .

"Ronk" refers to the count of non-zero elements in a matrix's reduced row form, unlike "rank," which counts non-zero rows. Ronk is not unique because RRFs can have varying distributions of zero and non-zero elements. This variability reveals that while rank is a definitive property describing a matrix's linear independence, other measures like ronk are not invariant across transformations .

Language derivation exercises exemplify reasoning that proves statements (validity of words) with strict rule sequences, similar to deriving properties in vector spaces via axiomatic systems. Such tasks cultivate skills in logical progression and symbolic manipulations, which are critical in formal proof strategies that demonstrate theorems or properties without relying on intuitive understanding .

The word "MU" is incorrect because it cannot be produced by the rules (R1)-(R5). The key reason for this is related to the divisibility of the number of I's in a word by three. Rule (R1) starts with one I, and no rule increases the number of I's to make their count divisible by three. "MU" contains zero I's, which is divisible by three. As per Rule (R6), only words produced by the first five rules are correct . Therefore, "MU" is deemed incorrect as it does not follow this structure.

You might also like