Programming Assignment 4: Computing the General Solution to Ax = y Solved

I want you to write a generic solver for a set of simultaneous equations Ax = y, where A is a known n m matrix and y is a known n 1 vector. You may wish to look at lesson 2 of my notes for the relevant theory. This assignment can take some time, please get started on it ASAP.

Here are the components your code:

    1. Check if there is a solution to Ax = y by testing if rank([A j y]) = rank(A).


    2. If there is no solution { report it as such. If there is a solution, then present the general solution to Ax = y.

You will need N EW M AT for this programming exercise. You might wish to look at linear algebra1.cpp, linear algebra2.cpp and linear algebra3.cpp on Com-pass to get started on this exercise. As you will see when you do this assignment (or, if you attended class regularly and listened attentively), you will need to pick rank(B)-many columns from a matrix B, at various instants. For this, you may wish to look at the C++ code provided with this assignment that computes n-take-k combinations of a set of n objects (where 1 k n).


If there is a solution to Ax = y, you will have to compute all possible basic solutions, where you pick rank(A)-many columns of A (call this matrix X; rank(X) = rank(A)) and then compute z according to equation 1 of lesson 2 of my notes. You then have to insert zeros into z at appropriate locations (depending on which columns of A where chosen to be in X). This augmented-version of z becomes one basic solution (you have several more, depending on how many candidates for X you have in any given case). Following this, you stack all basic solutions into one large matrix S and pick rank(S)-many columns of S (call this matrix T; rank(T) = rank(S)) and present the a ne combination of these columns as the general solution to Ax = y.

The input to your code should be read on command-line through a le. For example, the le input1 on Compass, which is shown in gure 1 presents the relevant details for the instance shown in equation 2 in page 4 of lesson 2 of my notes. The rst (second) entry in the le is the number of rows (columns) of A. Following this, each element of A is a presented in a row-by-row fashion. Finally, the entries of y are presented in a row-by-row manner. The format of the input le should be obvious with the example from equation 1 in page 4 of lesson 2 of my notes and what is shown in gure 1 . I am looking for an output along the lines of what is shown in gure 2 for this example. Note that the



1





output in    gure 2 says the general solution has the form
0
2 1
+(1   )0
3 1
=
0

B
1
C
B
3
C

B
3

0


1




B
3
C
B
0
C

B

@

A
@

A

@











2
3
1
:
(1)


C


3
1





C


A
I am also including a le called input2 on Compass that presents the relevant input for the problem in section 3.1 of lesson 2 of my notes. Figure 4 shows the sample output when my C++ code is run on input2. The output in gure 4 says the general solution has the form


0141

0 141


0
0 1







0
0 1
0


B
28
C

B
37
C


B
28
C







B
7
C
= B

1

15

+

0

+
3

15

+(1

1

2

)

15




B
0
C
2
B   C


B   C





3

B   C  B


B
0
C

B
3
C


B
0
C







B
0
C  B


B

C

B

C


B

C







B

C
B


B
0
C

B
0
C


B
7
C







B
0
C  B


B

C

B

C


B

C







B

C
B


B
0
C

B
0
C


B
0
C







B
7
C  B


B

C

B

C


B

C







B

C
B


@

A

@

A


@

A







@

A
@

35 1+44 2+35 3    7
14 1+14 2
7 3
15    15 2
3 2
7 3
7    72    73    71

1

C
C
C
C
    • :
C
C
C

A
(2)

The input    le shown in    gure 5 describes the equation that is just below

equation 2 in page 4 of lesson 2 of my notes. Figure 6 shows the result when

my code is run on this input    le.

Some Questions/thoughts...

Question: How do you reconcile the fact that while equation 1 looks similar to the general solution presented in page 7 of lesson 2 of my notes, equation 2 looks di erent from equation 6 in page 10 of lesson 2.














Figure 1: The format of the input le that describes the problem of equation 2 in page 4 of lesson 2 of my notes.


References



2






























Figure 2: Sample output when the le shown in gure 1 is presented as input. The general solution is presented as the a ne combination of the two solution vectors shown in the screen.























Figure 3: The format of the input le that describes the problem of section 3.1 of lesson 2 of my notes.




3



































Figure 4: Sample output when the le shown in gure 3 is presented as input. The general solution is presented as the a ne combination of the four solution vectors shown in the screen.

















Figure 5: The format of the input le that describes the problem just below equation 2 in page 4 of lesson 2 of my notes.




4







































Figure 6: Sample output when the    le shown in    gure 5 is presented as input.





















5