Mathematics desk
< May 24	<< Apr \| May \| Jun >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 25

Correctness of an Algorithm

Hi, I've invented some nice algorithm, and I want to know if it's correct :)

The Problem: Let A be a binary matrix of size $m\times n$ , such that A consists of exactly three 1's in each row, and the rest are 0's. Let $b=(1\dots 1)^{T}$ (a column vector whose entries are 1's). Is there a 0-1 solution to the equation $Ax=b$ That is, is there some binary vector x that satisfy $Ax=b$ ?

Notice: hereinafter, I will usually treat the equation $Ax=b$ as a system of linear equations, instead of one equation. Similarly, I sometimes call "A" a matrix, and sometimes I call it a system of linear equations.

Into to the Algorithm: Let f be a function that given some system of linear equation, f checks whether it holds that $x=y$ or $x=1-y$ over $\{0,1\}$ , simply by substituting all possibilities over $\{0,1\}$ , and adding the corresponding equations that represents each substitution, and finally f checks whether the new system of equations (=with the new equations that represent some substitution for x and y) has a solution over $\mathbb {R}$ or not.

For example, if when adding the equations $x=0,y=0$ or $x=1,y=1$ the obtained system of equations has no solution over $\mathbb {R}$ , and when adding the equations $x=0,y=1$ or $x=1,y=0$ there's some solution over $\mathbb {R}$ , then we can deduce that $x=1-y$ .

On the other hand, if when adding the equation $x=0,y=0$ there's some solution but when adding $x=1,y=1$ , there's no solution over $\mathbb {R}$ , then neither $x=y$ nor $x=1-y$ holds.

Additionaly, we check whether it holds over $\{0,1\}$ that x must be 0, or it must be 1 (again - by adding the corresponding equation, and cheching it there's some solution over $\mathbb {R}$ . If only when we add the equation $x=0$ , we obtain a system of equations that has a solution over $\mathbb {R}$ , and when we add $x=1$ we get a system of equations with no solution over $\mathbb {R}$ , then that means that x must me 0).

Afterwards, f checks some list of rules that say: "if the system of equations consists of some equation of the form ___, then add the equation __ to the system of equations, unless the latter equation already exists in the system of equations."

The idea is that these rules say to add equations that one can deduce from the system of equations over $\{0,1\}$ , so that by adding the new equation, one can deduce it from the obtained system of equation over $\mathbb {R}$ , too.

For example, one can deduce over $\{0,1\}$ from the equation $2x+y=1$ that $x=0$ . Therefore, there's some rule of the form $2x+1\to x=0$ .

In fact, one can also deduce over $\{0,1\}$ that $y=1$ , but we don't need to add the equation $y=1$ , since one can also deduce over $\mathbb {R}$ from the equations $2x+y=1$ and $x=0$ , that $y=1$ . So, it's sufficient to add the equation $x=0$ , and there's no need to add the equation $y=1$ , too.

Another example, the equation $2x=1$ has no solution over $\{0,1\}$ . So, we add another equation $x=0$ , because when adding the latter equation to the original system of equation (consists of the equation $2x=1$ only), yields a new system of equations that has no solution over $\mathbb {R}$ , too.

Notice that both $2x+y=1$ and $2x=1$ can't appear in our system of equations, since A is a binary matrix, and since each equation must consist of exactly 3 terms (because A has exactly three 1's in each row, as mentioned above). So, by talking about the equation $2x=1$ , for instance, I mean the equation $x+y+z=1$ after we found out that it holds over $\{0,1\}$ that $x=y$ , and $z=0$ .

Here's the full list of rules:

$2x+y=1\to x=0$
$x+y+1=1\to x=0$
$2x=1\to x=0$
$3x=1\to x=0$
${\begin{cases}x+y+a=1\\x+1-y+b=1\end{cases}}\to x=0$
${\begin{cases}x+y+z=1\\A+x+a=1\\A+y+b=1\\A+z+c=1\end{cases}}\to A=0$

The algorithm: We apply the function f repeatedly until we reach a fixed point. i.e, we apply f on the matrix A, and get some matrix B, and we apply it again, and we get C, etc., until we finally get some matrix M that satisfy $f(M)=M$ .

Statement: every linear equation over the variables of the original and the new system of equations (both are over the same variables) holds for all of the solutions of the original system of linear equations over $\{0,1\}$ iff the same equation holds for all of the solutions of the new system of linear equations over $\mathbb {R}$

"Proof": this is exactly what f does - f takes the information we have over $\{0,1\}$ , and creates a new system of equation such that we have this information over $\mathbb {R}$ , too. So, a fixed point of f means that there's no more information that we have over $\{0,1\}$ , and we don't have over $\mathbb {R}$ .

Corollary: the new system of linear equation has a solution over $\{0,1\}$ iff the original system of equations has a solution over $\{0,1\}$ .

Is that algorithm correct? Thanks in advance! :) עברית (talk) —Preceding undated comment added 05:49, 25 May 2016 (UTC)[reply]

From the system 3x=1 we reduce to x=0. The equation "x=1" holds (vacuously) for all {0,1}-solutions of the original system, but not for all real solutions of the reduced equation.

Also, I presume you are the same person as the IP who was asking about this a few days ago; did you see my final example there? --JBL (talk) 14:15, 25 May 2016 (UTC)[reply]

Maybe I wasn't clear - we only add equations; we don't replace the former equations with the new ones. So, regarding 3x=1, we get the system of equations

{\begin{cases}3x=1\\x=0\end{cases}}

, and this system of equations has no solution over

\mathbb {R}

, so x=1 holds vacuously for all solutions over

\mathbb {R}

, too.

Yes, I'm the same asker :)

I hadn't seen your final example before :|

However, your answers there (before this example) helped me to understand that I need some more powerful criterion\ algorithm, so now I came up with this :)

Although a counterexample to my statement there, I think that your final example isn't a counterexample to my statement here, since applying rule No. 5 on the first 2 equations there, we get b=0, and applying this rule again on the last 2 equations we get 1-b=0. So, the new system of equations has no real solution, as desired (it's desired since the original system of equations has no 0-1 solution)

Do you have a counterexample for this algorithm? עברית (talk) 05:30, 26 May 2016 (UTC)[reply]

I would not be deeply shocked if one of the two implications is true, but I don't see any real reason to believe that everything one can say is the result of local moves like this. It seems more likely to me that there exist large examples in which no reductions like this can be made but for which there are real solutions not related to any 0,1 solutions, or something. (In particular, my first instinct is to believe the original question is NP-complete.) I don't have any recipe for producing counter-examples, but you might consider creating a bunch of random equations on 15 variables or something to see what happens. --JBL (talk) 14:26, 26 May 2016 (UTC)[reply]

@עברית: Ok, I got bored at work, here's an example:

1 + x[2] + x[15] - x[18] == 1, 2 + x[4] - x[12] - x[18] == 1, 
2 - x[3] - x[14] + x[17] == 1, x[10] + x[11] + x[16] == 1, 
2 - x[1] + x[5] - x[15] == 1, 2 + x[2] - x[3] - x[4] == 1, 
x[1] + x[6] + x[13] == 1, 2 - x[11] - x[18] + x[19] == 1, 
3 - x[9] - x[12] - x[14] == 1, 2 - x[6] - x[8] + x[16] == 1, 
1 + x[6] + x[9] - x[10] == 1, 1 + x[1] + x[12] - x[20] == 1, 
x[8] + x[9] + x[17] == 1, 1 - x[3] + x[8] + x[11] == 1, 
2 - x[5] - x[7] + x[10] == 1, 1 + x[8] - x[12] + x[15] == 1, 
1 + x[10] + x[13] - x[14] == 1, x[3] + x[19] + x[20] == 1, 
1 + x[1] + x[7] - x[8] == 1, 2 - x[4] + x[14] - x[19] == 1

More generally, take a random set of n equations in n variables for n large enough. Generically, this system will have a unique real solution but no solution in {0, 1}, no equation will have a variable repeated, no two equations will agree in more than one variable, and no set of 4 equations will have the form of your rule 6. (I mean, I haven't written proofs of these things but it would be deeply shocking if any of them were false.) So a typical large situation is that your algorithm does nothing, but the real solutions are not the {0, 1} solutions. (I think the example above, with 20 equations on 20 variables, is like this.) I think you would have better luck proving that this problem is NP-complete. --JBL (talk) 00:52, 27 May 2016 (UTC)[reply]

I agree that it's a counterexample for my original statement.

However, what happens if changing my algorithm (at the last time, I promise :)), and instead of the rules

2x=1

and

3x=1

, we just say that if some variable, x, is fixed in all the solutions of the system to some value

v\not \in \{0,1\}

, then there's no 0-1 solution.

This is just a little change in the algorithm, but then - examples like the above mentioned one, fail (since they have a unique real solution).

Does this variation of the algorithm work? עברית (talk) 14:29, 27 May 2016 (UTC)[reply]

My instinct (and that is all it is) is that we can still break this by taking n − 1 equations in n variables for n large enough. Again generically, the system will be compatible with x = 0 or x = 1 separately for each variable x. Maybe just delete one equation from the example above? --JBL (talk) 18:09, 27 May 2016 (UTC)[reply]

Your problem appears to be exactly-1 3-satisfiability, which is NP-complete. -- BenRG (talk) 22:21, 27 May 2016 (UTC)[reply]

Thank you both for telling me it's NP-complete! עברית (talk) 20:20, 28 May 2016 (UTC)[reply]

Solving a shape that looks like a parallelogram, but isn't marked as one

I have a maths quiz question involving a four sided shape where I know two angles (both on one side) and the non-adjacent side length. I also know the two shorter adjacent side lengths are parallel, but not how long they are. Is it actually solveable from that information? I am wondering if it's a misprint, and was meant to be a real parallelogram (ie parallel on its long sides as well as the short ones). 82.6.151.23 (talk) 09:57, 25 May 2016 (UTC)[reply]

Not sure about the phrase "adjacent side lengths are parallel". Did you mean the adjacent sides are parallel and have the same length? If so then you've got a parallelogram. If you don't know anything about the lengths but only know the sides are parallel (which you could deduce from the given angles), then you have a trapezium (UK usage since you call it maths). --RDBury (talk) 12:34, 25 May 2016 (UTC)[reply]

Yes. I'm British, and for us this shape is a trapezium. I'd forgotten the word. 82.6.151.23 (talk) 18:52, 25 May 2016 (UTC)[reply]

A quadrilateral (four sided shape) on a plane (flat surface) has 5 degrees of freedom. In other words, you need five independent pieces of information to define the shape of the quadrilateral uniquely. If you know that two opposite sides are parallel then that is one piece of information. Together with two known angles and one known side length you have at most four pieces of information, which is not enough to give a unique solution.

On the other hand, if you have a parallelogram then you know that both pairs of opposite side are parallel, which is two pieces of information. But now knowing two angles only gives you one more piece of information because any two adjacent angles in a parallelogram sum to 180 degrees, so angles are not independent. Together with one known side length, you still only have four pieces of information. So solution is still not unique. Gandalf61 (talk) 13:23, 25 May 2016 (UTC)[reply]

To the OP: if you want to communicate a diagram in text, the usual convention is to label the vertices. Then you can refer unambiguously to angles and edges.

Separately, at least in the U.S. it would be unusual for "go ask people on the internet for help with a quiz" to be compatible with rules about academic honesty. --JBL (talk) 15:06, 25 May 2016 (UTC)[reply]

I take your point, but please note that I haven't posted any values for anyone to evaluate, and haven't asked for step by step instructions. All I'd like to find out here is if I have enough information to try to find a solution, and perhaps the name of the technique I should be using. This is an open book quiz btw, and I can pass without the marks for this question. I'm just mystified by it, and still wondering if it's a misprint because as far as I understand things, I don't have enough information to solve it unless both pairs of lines were meant to be marked parallel. 82.6.151.23 (talk) 18:52, 25 May 2016 (UTC)[reply]

So, by my understanding, for a quadrilateral A,B,C,D (labeled clockwise), you have angles a and b, side length CD, and know that BC and AD are parallel (and possibly that they are shorter than AB or CD)? What do you actually need to find out about the quadrilateral? I can't see any other piece of information which you could get with just those values, so it seems likely that there is some information missing - in your description or the question. MChesterMC (talk) 15:49, 25 May 2016 (UTC)[reply]

You're right about all the details, and I'm sorry if my question was hard for anyone to follow. I didn't know how to describe the diagram; now I do :-)

What I was asked to find is the side of a triangle next to the shape I mentioned. One of its other sides is the line CD. All I know about it is two side lengths, so the only way I could think of to proceed would be solving the trapezium, which would give me some corresponding angles and let me use the cosine rule. 82.6.151.23 (talk) 18:52, 25 May 2016 (UTC)[reply]

OK, a couple more questions: Let's call the point of the triangle Q (i.e. the point opposite CD). Is either of ADQ or BCQ a straight line? And if so, which of the side lengths DQ and CQ do you know? I think you still need another angle to solve it - is there no other information? Any symbol on the diagram which indicates that the other pair of sides is parallel, or that shows one of the angles to be a right angle? Edit: Just to clarify, the parallel symbol is typically a number of slanted lines crossing the line, and the right angle symbol is typically a small box on the angle.MChesterMC (talk) 08:15, 26 May 2016 (UTC)[reply]

ADQ is a straight line, but BCQ isn't. I know the lengths of CD and DQ, but no angles, and I've been asked to find CQ. The diagram looks like AB and CD should be parallel, but there is definitely no symbol to say so, and no right angles either. I already handed in my quiz with this question left blank, btw, so it doesn't matter in terms of marks but I'd still like to find the answer! 82.6.151.23 (talk) 12:03, 30 May 2016 (UTC)[reply]