Two lines are indeed enough.

# Build a hash of word counts
foreach ( map @$_, @all ) { $words{$_} ++ }

# Create a list of arrays showing repeats
@out = map { [ map $words{$_} > 1 ? 1 : 0, @$_ ] } @all;
[download]

With regards to map, I find it easiest to think of it as a rolled-up form of the common foreach ... push idiom:

# List processing with foreach/push  
foreach ( @input ) {
  push @out, lc($_);
}
print @out;

# Equivalent "rolled-up" map expression:
print map { lc($_) } @input;
[download]

++ because It took me some time to figure out how your solution works.

#!/usr/bin/perl -w

use strict;

use vars qw(@all @dup);

@all=(["what", "is", "the", "matrix"],["matrix", "reloaded", "is", "no
+", "good"]);

my(%h1,%h2); # for the two halves of your array
grep { $h1{$_}=1 } @{$all[0]};
grep { $h2{$_}=1 } @{$all[1]};

@dup = ( [ map { $h2{$_} ? 1 : 0 } @{$all[0]} ],
         [ map { $h1{$_} ? 1 : 0 } @{$all[1]} ]);
print '([',
      join(',',@{$dup[0]}),
      '], [',
      join(',',@{$dup[1]}),
      "])\n";
[download]

I would write this

grep { $h1{$_}=1 } @{$all[0]};
[download]

like this

grep { $h1{$_}=1; undef; } @{$all[0]};
[download]

in order not to get all my elements from @{$all[0]} as a return value of grep.

I even might write:

@h1{@{$all[0]}}=(1) x @{$all[0]};
[download]

Why use grep at all if you don't need a return value?

$h1{$_}=1 for @{$all[0]};
[download]

use strict;
use warnings;
use Data::Dumper;

my @erg;
my @all=(["what", "is", "the", "matrix"],["matrix", "reloaded", "is", 
+"no", "good"]); 
print "\n",Dumper(\@all);

for (my $i = 0; $i < @{$all[0]}; $i++) {
    for (my $j = 0; $j < @{$all[1]}; $j++) {
        $erg[0][$i] ||= sprintf "%u", ($all[0][$i] eq $all[1][$j]);
        $erg[1][$j] ||= sprintf "%u", ($all[0][$i] eq $all[1][$j]);
    }
}

print "\n",Dumper(\@erg);
[download]