Induction Proof for 2^n x 2^n Matrix Using L Transformation

[Jairo Rojas]

Homework Statement

Attached is the problem

Homework Equations

The Attempt at a Solution

The trick to solve this problem is that when we assume that it is true for a 2^n x 2^n matrix and then we expand this matrix with 1's to a 2^n+1 x 2^n+1, we can divide the resulting matrix into 4 submatrices of 2^n x 2^n. 1 matrix will be crossed out already but the other 3 will have just 1 entries. To apply the inductive step on the 3 left matrices, we just perform an L transformation on the corner of the solved sub matrix. Now every left submatrix will have a 0. Therefore, they can be crossed by inductive hypothesis. My problem is that I don't know how to state formally that we can cross that specific L.

 

[SammyS]

Homework Statement

Attached is the problem

Homework Equations

The Attempt at a Solution

The trick to solve this problem is that when we assume that it is true for a 2^n x 2^n matrix and then we expand this matrix with 1's to a 2^n+1 x 2^n+1, we can divide partition the resulting matrix into 4 submatrices of 2^n x 2^n. 1 matrix will be crossed out already but the other 3 will have just 1 entries. To apply the inductive step on the 3 left remaining matrices, we just perform an L transformation on the corner* of the solved sub matrix. Now every left remaining submatrix will have a 0. Therefore, they can be crossed by inductive hypothesis. My problem is that I don't know how to state formally that we can cross that specific L.

* At the corner where the four submatrices meet there are four elements (one from each submatrix). One of these is a zero. Each of the other three is a 1 and together form an "L". ...

 

[Jairo Rojas]

* At the corner where the four submatrices meet there are four elements (one from each submatrix). One of these is a zero. Each of the other three is a 1 and together form an "L". ...

thanks!

 

[Ray Vickson]

Homework Statement

Attached is the problem

Homework Equations

The Attempt at a Solution

The trick to solve this problem is that when we assume that it is true for a 2^n x 2^n matrix and then we expand this matrix with 1's to a 2^n+1 x 2^n+1, we can divide the resulting matrix into 4 submatrices of 2^n x 2^n. 1 matrix will be crossed out already but the other 3 will have just 1 entries. To apply the inductive step on the 3 left matrices, we just perform an L transformation on the corner of the solved sub matrix. Now every left submatrix will have a 0. Therefore, they can be crossed by inductive hypothesis. My problem is that I don't know how to state formally that we can cross that specific L.

Please get out of the habit of posting attachments stating the problem/solution, unless the problem or solution is complicated or involves diagrams, etc. Your problem can be stated simply and that should be done right in the input panel.

Most PF helpers will not look at attachments as you are employing them.

You should read the post by Vela entitled "Guidelines for students and helpers", which is pinned to the start of the sub-forum.

 

[Jairo Rojas]

Please get out of the habit of posting attachments stating the problem/solution, unless the problem or solution is complicated or involves diagrams, etc. Your problem can be stated simply and that should be done right in the input panel.

Most PF helpers will not look at attachments as you are employing them.

You should read the post by Vela entitled "Guidelines for students and helpers", which is pinned to the start of the sub-forum.

Ok, I will keep that in mind for the future.