First, making a 100x100 matrix sparse is silly. Flat out, silly. The amount of time needed to solve that system is tiny, even as a full matrix.
Is A no longer singular as you have formed it?
Not even close to singular. And that means any column permutations will have no impact on the solution.
It took fractions of a millisecond to solve. In full form, is it any different?
Virtually, NO. So unless your real problem is wildly larger, then you are wasting your time with this entire effort to make A sparse, or for that matter, to use column permutations to reduce fill-in. Even if you made this a 1000x1000 problem, the direct full solve will still be blazingly fast.
It would help if you tell us how large your real problem is, or why you so desperately want to solve this problem as you are doing it.
Even without that, you still clearly have a problem in how you employed the column permutaiton.
[L,U] = lu(A); x1 = U\(L\b);
x1 is computed correctly. Now let me look at how you are computing x2, using the column permutation.
What does a column permutation mean?
Imagine we want to solve the problem A*x = b. We will do this by a permutation of the columns of A. But that does NOT involve permuting the rows of b!!!!!!!
A permutaiton of the columns of A is equivalent to a re-ordering the elements of x in that problem. That is, we expect that if x is a solution of A*x=b, and p is a column permutation of A, then we would have
A*x == A(:,p)*x(p)
There is no need to permute the elements of b, nor do you want to do so.
Which works perfectly ok. The tiny difference is on the order of cond(A)*eps.
And that is why you had a problem. For some strange reason, you decided you needed to permute the elements of b. You are still wasting your time with the permutation in the first place on this tiny problem, but maybe your real problem is seriously, massively larger. Who knows?