Linear Algebra Assignment 3 Solution: SIT292, Matrices, and Codes

This document presents a complete solution to a Linear Algebra assignment (SIT292), addressing several key concepts. The solution begins by determining the row-rank of a given matrix and identifying the basis for its row space. It then proceeds to calculate the eigenvalues and corresponding eigenvectors of a matrix, followed by the application of the Gram-Schmidt procedure to obtain orthonormal vectors. The assignment further explores subspaces, proving that a given set forms a subspace and determining its dimension and basis. Finally, the document delves into linear binary codes, constructing a generator matrix, generating code words, and computing the parity check matrix and syndromes for received words. Each question is solved with detailed steps and explanations, providing a thorough understanding of the concepts involved.

SIT292 LINEAR ALGEBRA
ASSIGNMENT- 3
STUDENT ID
[Pick the date]

Question 1
Given matrix
(a) Row- rank of matrix
In order to determine the rank of the above matrix, it is essential to transform the matrix into
upper triangular matrix with the help of row operations.
1

It can be seen from the above upper triangular matrix that there is three non-zero rows and hence,
the row- rank of matrix A is 3.
(b) Set of generators for the row space of A is highlighted below:
{ (1 2−3 0 ) ( 2 4−2 2 ) ( 36−4 3 ) }
(c) Basis for the row space of matrix A
It is apparent that all the three rows of the given matrix A are linearly independent because the
row rank of the matrix is three. Further, these three rows will make the basis for the respective
row spaces. Therefore, the basis of the row space is shown below:
{ (1 2−3 0 ) ( 2 4−2 2 ) ( 36−4 3 ) }
Therefore, the generator and the basis vectors are the same for the given problem.
Question 2
Given matrix
Let A=
[0 2 0
1 0 1
0 2 0 ]
(a) Eigenvalue
2

Eigenvalues would be the roots of the matrix which would be determined by using the
determinant of ( A−λ I )=0
( A−λ I ) =
[ 0 2 0
1 0 1
0 2 0 ] −λ [ 1 0 0
0 1 0
0 0 1 ]
( A−λ I )=
[0 2 0
1 0 1
0 2 0 ]−
[ λ 0 0
0 λ 0
0 0 λ ]
( A−λ I )=
[−λ 2 0
1 −λ 1
0 2 −λ ]
det ( A−λ I )=
|−λ 2 0
1 −λ 1
0 2 −λ|
¿−λ ( λ2−2 )−2 (−λ−0 )+ 0(2+λ)
¿−λ ( λ2−2 )+2 λ+0
¿−λ3+ 2 λ+ 2 λ
¿−λ3+ 4 λ
¿−λ ( λ2−4 )
¿−λ ( λ−2 ) ( λ+2 )
Now, put det ( A−λ I )=0
−λ ( λ−2 ) ( λ+2 ) =0
λ=0 , 2 ,−2
3

Hence, the eigenvalues of the given matrix is 0 , 2 ,−2.
4

(b) Eigenvector corresponding to eigenvalues
 Eigenvector corresponding to eigenvalues λ = 0
( A−λ I ) =
[ 0 2 0
1 0 1
0 2 0 ] −0 [ 1 0 0
0 1 0
0 0 1 ]
¿ [0 2 0
1 0 1
0 2 0 ]−
[0 0 0
0 0 0
0 0 0 ]
¿ [ 0 2 0
1 0 1
0 2 0 ]
Reduce the matrix into row echelon form
[ (a ⋯ b
0 ⋱ ⋮
0 0 c ) ]
¿ [ 1 0 1
0 2 0
0 0 0 ]
Reduce the matrix to reduced row echelon form
[ (1 ⋯ b
0 ⋱ ⋮
0 0 1) ]
¿ [ 1 0 1
0 1 0
0 0 0 ]
Now,
5

( A−λ I ) ( x
y
z )=
(0
0
0 )
( A−0 I ) ( x
y
z ) =
( 0
0
0 )
[ 1 0 1
0 1 0
0 0 0 ] ( x
y
z )=
( 0
0
0 )
x + z=0
y=0
In isolated form
y=0
x=−z
Now, let assume z = 1
Eigenvector v=
(−z
0
z )= (−1
0
1 )
 Eigenvector corresponding to eigenvalues = 2
( A−λ I )=
[0 2 0
1 0 1
0 2 0 ]−2 [1 0 0
0 1 0
0 0 1 ]
¿ [0 2 0
1 0 1
0 2 0 ]−
[2 0 0
0 2 0
0 0 2 ] 6

¿ [−2 2 0
1 −2 1
0 2 −2 ]
Reduce the matrix into row echelon form
[ (a ⋯ b
0 ⋱ ⋮
0 0 c ) ]
¿ [
−2 2 1
0 2 −2
0 0 0 ]
Reduce the matrix to reduced row echelon form
[ (1 ⋯ b
0 ⋱ ⋮
0 0 1) ]
¿ [ 1 0 −1
0 1 −1
0 0 0 ]
Now,
( A−λ I ) ( x
y
z )=
(0
0
0 )
( A−2 I ) ( x
y
z )= (0
0
0 )
[1 0 −1
0 1 −1
0 0 0 ] ( x
y
z )=
(0
0
0)
x−z=0
7

y−z =0
In isolated form
x=z
y=z
Now, let assume z = 1
Eigenvector v=
( z
z
z )= ( 1
1
1 )
 Eigenvector corresponding to eigenvalues = -2
( A−λ I )=
[0 2 0
1 0 1
0 2 0 ]−(−2) [1 0 0
0 1 0
0 0 1 ]
¿ [0 2 0
1 0 1
0 2 0 ]−
[−2 0 0
0 −2 0
0 0 −2 ]
¿ [2 2 0
1 2 1
0 2 2 ]
Reduce the matrix into row echelon form
[ (a ⋯ b
0 ⋱ ⋮
0 0 c ) ]
¿ [ 2 2 0
0 2 2
0 0 0 ]
Reduce the matrix to reduced row echelon form
8

[ (1 ⋯ b
0 ⋱ ⋮
0 0 1) ]
¿ [ 1 0 −1
0 1 1
0 0 0 ]
Now,
( A−λ I ) ( x
y
z )=
(0
0
0 )
( A−(−2) I ) ( x
y
z )=
(0
0
0)
[1 0 −1
0 1 1
0 0 0 ] ( x
y
z )=
(0
0
0)
x−z=0
y + z=0
In isolated form
x=z
y=−z
Now, let assume z = 1
Eigenvector v=
( z
−z
z )= ( 1
−1
1 )
9

Therefore, the eigenvector of the matrix is (−1
0
1 ), (1
1
1 ), ( 1
−1
1 )
(c) Set of orthonormal vectors with the help of Gram-Schmidt Procedure
Computed eigenvector of the matrix is (−1
0
1 ), (1
1
1 ), ( 1
−1
1 )
Let
x= (
−1
0
1 )
y= (1
1
1 )
z= ( 1
−1
1 )
Gram-Schmidt Procedure
u= y− ¿ x , y > x
¿ y , y >¿ ¿
u= ( 1, 1 ,1 ) − ¿ (−1,0,1 ) , ( 1 ,1 , 1 ) > x
¿ x , x>¿= ( 1,1,1 ) ¿
It is apparent that that eigenvector corresponding to distinct eigenvalues are orthogonal and
hence, {x , y , z } are orthogonal vectors.
Hence,
10

{ x
||x|| , y
|| y|| , z
||z|| } are orthonormal vectors .
Thus,
Final Solution: Orthogonal vectors
Question 3
11

The set of ordered triples which forms a basis for R3 .
{ ( 1,0,1 ) , (−1,1,1 ) , ( 0,1,0 ) }
Gram-Schmidt Procedure to construct an orthogonal basis for R3
Let
x1= ( 1 , 0 ,1 )
x2= ( −1,1,1 )
x3= ( 0 , 1,0 )
Now,
v1 =x1
v2=x2 −¿ x2 . v1 > ¿
¿ v1 . v1 >¿ v1 ¿ ¿
v3 =x3−¿ x3 . v1 > ¿
¿ v1 . v1> ¿ v1−¿ x3 . v2> ¿
¿ v2 . v2 >¿ v2 ¿ ¿ ¿ ¿
Further,
v1 =x1 = ( 1, 0 , 1 )
v2= (−1,1,1 )− (−1,1,1 ) . ( 1 , 0 ,1 )
( 1 , 0 ,1 ) . ( 1 ,0 , 1 ) (1 , 0 , 1 )
v2= ( −1,1,1 ) − 0
2 ( 1 , 0 , 1 ) = ( −1,1,1 )
v3 =x3−¿ x3 . v1 > ¿
¿ v1 . v1> ¿ v1−¿ x3 . v2> ¿
¿ v2 . v2 >¿ v2 ¿ ¿ ¿ ¿
12

¿ ( 0 , 1,0 ) − ( 0 ,1,0 ) . ( 1 , 0 ,1 )
( 1 , 0 ,1 ) . ( 1, 0 , 1 ) ( 1 , 0 ,1 ) − ( 0 ,1,0 ) . ( −1,1,1 )
( −1,1,1 ) ( −1,1,1 ) ( −1,1,1 )
¿ ( 0 , 1,0 )−0− 1
3 (−1,1,1 )
¿ ( 0 , 1,0 ) − ( −1
3 , 1
3 , 1
3 )
¿ ( 1
3 , 2
3 , −1
3 )
w=span {( 1 , 0 , 1 ) , (−1,1,1 ) , ( 1
3 , 0 , −1
3 ) }
For Orthonormal Basis
|¿ v1|∨¿ √ 12 +02+12= √2
|¿ v2|∨¿ √ (−1)2 +12 +12= √ 3
|¿ v3|∨¿ √ ( 1
3 )
2
+( 2
3 )
2
+ ( −1
3 )
2
= √ 1
9 + 4
9 + 1
9 = √ 2
3
Orthonormal Basis
{ w1 , w1 , w1 }
{ v1
||v1|| , v2
||v2|| , v3
||v3||}
W 1= v1
||v1||
= ( 1, 0 , 1 )
√ 2 =
( 1
√ 2 , 0 , 1
√ 2 )
13

W 2= v2
||v2||
= ( −1,1,1 )
√ 3 =
( −1
√ 3 , 1
√ 3 , 1
√ 3 )
W 3= v3
||v3||
= ( 1
3 , 2
3 , −1
3 )
√ 2
3
= ( 1
√ 6 , √ 2
3 ,− 1
√ 6 )
Therefore, the orthonormal basis for R3 is {( 1
√2 , 0 , 1
√2 ), (−1
√3 , 1
√3 , 1
√3 ), ( 1
√6 , √ 2
3 ,− 1
√6 ) }
Question 4
(a) Need to prove that V is a subspace of R4
V = ( 0,1,−2,1 )
Assume that V ={( x , y , z , w ) ∈ R4 : ( x , y , z , w ) is orthogonal ¿ ( 0,1 ,−2,1 )
Now,
( x , y , z , w ) T . ( 0,1,−2,1 ) =0
( x∗0 ) + ( y∗1 ) + ( z∗ ( −2 ) ) + ( w∗1 ) =0
y−2 z +w=¿
y=2 z−w … … … … … … .. ( 1 )
Let
14

m , n∈ V
And
∝∈ R
∝ m+n ∈ V (we need to show this)
Since,
m , n∈ V ∧α ∈ R
Hence , mT V =0 also , nT V =0 … … … .(2)
Further,
¿( ∝m+n)T V
¿ ( ∝ mT +nT )V
¿ ∝ mT V +nT V
From equation (2)
¿ 0+0=0
This indicates that ∝ m+n ∈ V ∧hence ,V is a subsapce of R4 .
(b) Dimension of V and basis of V needs to be determined.
V = { ( x , y , z , w ) ∈ R4 : ( x , y , z , w )T ( 0,1,−2,1 )=0 }
Based on equation (1) from part (a) it can be written as
y=2 z−w … … … … … … .. ( 1 )
15

¿ ¿
¿ { x ( 1,0,0,0 ) + z ( 0 , 2 ,1,0 ) + w ( 0 ,−1,0,1 ) }
It is apparent that { x ( 1,0,0,0 ) + z ( 0 , 2 ,1,0 ) + w ( 0 ,−1,0,1 ) } is a linearly independent set and also an
also the four vector space V. Hence,
B= { (1,0,0,0 ) , ( 0 , 2 ,1,0 ) , ( 0 ,−1,0,1 ) }
This B is termed as basis for the V.
Further, since B contains the three vectors and hence, the dimension of V is 3.
Question 5
Dimension of the subspace of R4 =?
Set of 4-tuples:
{ ( 1,2,1,2 ) , ( 2,4,3,5 ) , ( 3,6,4,9 ) , ( 1,2,4,3 ) }
Gaussian elimination method (row operation) has been used to reduce the matrix.
16

17

This is the possible reduced row echelon form of the given set of 4- tuples and hence, the
remaining vectors (rows) would be linearly independent.
Therefore, the originally given set of 4 tuples or say subspace can be written in the form of
spanning set of linearly independent vectors which are listed below:
{ ( 1,2,0,0 ) , ( 0,0,1,0 ) , ( 0,0,0,1 ) } This has dimension of three (3).
Question 6
Given code words
u1=1010010
u2=1100001
u3=0101000
u4=0010100
Basis for a (7, 4) linear binary code
(a) Generator matrix for the given code
A k × n matrix whose row derive a basis of a linear [n, k] and the code C would be termed as
generator matrix of C.
Now,
18

In this case, it can be seen that all the four rows are linearly independent. Further, any of the
rows cannot be written as a linear combination of the rest of the other three rows and therefore,
the generator matrix for the given code is shown below:
(b) Construction of code words for messages 1001 and 0101
 For message 1001
Let the message is u= ( u1 ,u2 , u3 ,u4 ) and the code word V for the given message u=1001
Then,
V =1. G ( 1, : )+ 0.G ( 2 ,: ) +0.G ( 3 , : ) +1. G ( 4 : )
¿ 1. G ( 1 , : ) +1. G ( 4 : )
¿ 1010010+0010100
¿ 1010110
 For message 0101
19

V =0.G ( 1 ,: )+1.G ( 2 ,: ) +0.G ( 3 , : ) +1. G ( 4 : )
¿ 1. G ( 2 , : ) +1. G ( 4 : )
¿ 1100001+0010100
¿ 1110101
(c) Parity check matrix for the given code
Generator matrix (G) for an [n, k]
Standard form: G=[ Ik ∨P ]
Parity check matrix: H= [−PT
|In−k ¿The
This is because G HT=P−P=0
Hence, parity check matrix (H)
(d) Computation of syndromes for the received words
1110011
1001010
20

0001101
1101010
Let
r =[r1 ,r 2 , r3 , r4 , r5 ,r6 , r7 ]
Where, r is a received word and A syndrome for the respective received word r is S which is
shown below:
S= [ S1 , S2 , S3 ] =r HT
Thus,
[ S1 , S2 , S3 ] = [ r1 , r2 ,r 3 , r4 , r5 , r6 , r7 ]
Transpose of parity check matrix is shown below:
Now,
S= [ S1 , S2 , S3 ] =r HT
[ S1 , S2 , S3 ]=[r1 , r2 , r3 , r 4 ,r5 , r6 , r7 ]
21

S1=r 4 +r5
S2=r1+ r6
S3=r2+ r7
(i) For 1110011
r = [ r1 ,r2 , r3 ,r 4 , r5 , r6 , r7 ]=[1110011]
S1=r 4 +r5= ( 0+0 ) =0
S2=r1+ r6= ( 1+1 ) =2
S3=r2+ r7= ( 1+1 ) =2
S= [ 0 ,2 , 2 ]
 For 1001010
r = [ r1 ,r2 , r3 ,r 4 , r5 , r6 , r7 ]=[1001010]
S1=r 4 +r5= ( 1+0 ) =1
S2=r1+ r6= ( 1+1 ) =2
S3=r2+ r7= ( 0+ 0 ) =0
S= [ 1 , 2 ,0 ]
 For 0001101
22

r = [ r1 ,r2 , r3 ,r 4 , r5 , r6 , r7 ]=[0001101]
S1=r 4 +r5= ( 1+1 ) =2
S2=r1+ r6= ( 0+0 ) =0
S3=r2+ r7= ( 0+1 ) =1
S= [ 2 , 0 , 1 ]
 For 1101010
r = [ r1 ,r2 , r3 ,r 4 , r5 , r6 , r7 ]=[1101010]
S1=r 4 +r5= ( 1+0 ) =1
S2=r1+ r6= ( 1+1 ) =2
S3=r2+ r7= ( 1+0 ) =1
S= [ 1 , 2 ,1 ]
23